[백준/C++] 11055번: 가장 큰 증가 부분 수열

11055번: 가장 큰 증가 부분 수열 문제 바로가기

문제 분석

수열의 크기 N이 주어지고, 해당 수열이 주어질 때, 합이 가장 큰 증가 부분 수열의 합을 출력하는 문제

---

문제 풀이 과정

예제를 생각하면서 풀이과정을 생각해보자.

1 100 2 50 60 3 5 6 7 8

1. 1

2. 1 + 100 vs 1

3. 1 + 100 vs 1 + 2

4. 1 + 100 vs 1 + 2 + 50

   …

5. 1 + 100 vs 1 + 2 + 50 + 60 vs 1 + 2 + 3 + 5 + 6 + 7 + 8

흠 .. 각 인덱스마다 크기비교를 해주면서 그 앞에 값들도 저장을 해줘야 할 것 같다 .. 어떻게 해야할까 ?

1. 0 ~ N 돌면서 dp[i]에 수열 A[i] 값을 저장
2. 0 ~ i 까지 돌면서 A[i]보다 작은 값이 있으면 해당 dp[0~i] + A[i]랑 dp[i]값 중에 갱신

3. ans = max(ans, dp[i]) 갱신

---

코드

#include <iostream>
#include <algorithm>
using namespace std;

int N, ans;
int A[1001], dp[1001];

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    
    for (int i = 0; i < N; i++) {
        dp[i] = A[i];
        for (int j = i; j >= 0; j--) {
            if (A[i] > A[j]) {
                dp[i] = max(dp[i], A[i] + dp[j]);
            }
        }
        ans = max(ans, dp[i]);
    }
    
    cout << ans;
    
    return 0;
}