백준 11055. 가장 큰 증가 부분수열

www.acmicpc.net/problem/11055

11055번: 가장 큰 증가 부분 수열

tose33.tistory.com/21

가장 긴 증가 부분 수열 문제와 유사.

이전 숫자와 비교하면서 가장 큰값 계속 갱신하면 된다.

 

#include <iostream>
using namespace std;

int a[1001];
int d[1001];

int main() {
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++) cin >> a[i];
    d[1] = a[1];
    int ans = a[1];

    for(int i = 2; i <= n; i++) {
        int max_sum = 0;
        for(int j = 1; j < i; j++) {
            if(a[j] < a[i]) {
                max_sum = max(max_sum, d[j]);
            }
        }
        d[i] = max_sum + a[i]; // 자신의 값까지 더한것이 d[i]
        ans = max(ans, d[i]); // 최대값 계속 생신
    }

    cout << ans;
}