[BOJ 11055] 가장 큰 증가하는 부분 수열

DP 기본 문제이다.

$O(N^2)$ 으로 풀 수 있는데, 원소를 하나 택하고, 그 전 원소들을 돌아보면서 현재 원소보다 작으면 이걸 더하면 된다. 

근데 이러면 1, 1, 2 같은 상황이 문제가 생기는데 그럼 1, 1은 증가하는 수열이 아닌데 2 기준에선 1, 1에서 증가하기 때문에 1 + 1 + 2 = 4 가 답이 나오게 된다. 그래서 dp 배열이 하나 필요한데, $dp[i]$ 를 i번째 원소를 더했을 때 가장 큰 증가하는 부분 수열 이라고 정의 하자.그럼 i번째 원소 이전에 j번째 원소를 돌아볼 때 합이 가장 큰 애만 더해줄 수 있고, 1, 1 과 같이 똑같은 수가 중복되는 상황도 해결할 수 있다. (dp[2] = 1, dp[1] = 1이 되니까). 

#include <bits/stdc++.h>
using namespace std;
int N, A[1001], dp[1001];
void solve() {
    int ans = 0;
    for(int i = 0; i < N; i++) {
        dp[i] = A[i];
        for(int j = 0; j < i; j++) 
            if(A[j] < A[i] && dp[i] < dp[j] + A[i])
                dp[i] = dp[j] + A[i];
        ans = max(ans, dp[i]);
    }
    cout << ans;
}
int main() {
    cin >> N;
    for(int i = 0; i < N; i++) cin >> A[i];
    solve();
}