[BAE/<JOON> 문제풀이] 11055. 가장 큰 증가 부분 수열 (DP.021)

https://www.acmicpc.net/problem/11055

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

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    struct node {
        int index, sum;
    };
    vector<int> arr;
    int n;
    vector<node> dp;
    cin >> n;
    arr.resize(n + 1);
    dp.resize(n + 1);  
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        dp[i] = { 1, arr[i] };
    }
    //dp[i] = i번째 까지의 증가수열중 마지막 값.
    
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i - 1; j++) {
            if (arr[i] > arr[j]) {
                if (dp[i].sum < dp[j].sum + arr[i]) {
                    dp[i].sum = dp[j].sum + arr[i];
                }
            }           
        }
    }
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        if (mx < dp[i].sum) {
            mx = dp[i].sum;
        }
    }
    cout << mx << endl;
    return 0;
}