[백준][DP] 가장 큰 증가 부분 수열

1. 문제 주소

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

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

2. 문제

i번째 숫자를 마지막으로 하는 증가하는 부분 수열의 합을 구하면 쉽게 풀 수 있다.

3. 소스코드

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int n;
    cin >> n;
 
    vector<int> A(n);
 
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
 
    vector<int> dp(n);
    int result = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = A[i];
        for (int j = 0; j < i; j++) {
            if (A[i] > A[j] && dp[j] + A[i] > dp[i]) {
                dp[i] = dp[j] + A[i];
            }
        }
        if (result < dp[i])
            result = dp[i];
    }
    cout << result << '\n';
    return 0;
}