11055번

11055번 - 가장 큰 증가하는 부분 수열

11053번인 가장 긴 증가하는 부분 수열과 똑같은 문제.

D[N] = N번째 수를 포함하는 가장 큰 증가하는 부분 수열 

이라는 점화식을 세운후, 값을 구한다.

D[N] 은 항상 A[N] 이상의 값이 되어야 하므로, 캐시 조건을 D[n] != A[n] 이라고 하면 한번 이상 계산된 D[N] 값만 리턴된다.

#include<iostream>
#include<algorithm>
#include<string.h>
 
using namespace std;
int A[1001];
int D[1001];
int N;
int ans;
int go(int n)
{
    if (D[n] != A[n])
    {
        return D[n];
    }
 
    for (int i = 1; i < n; i++)
    {
        if (A[n] > A[i])
        {
            D[n] = max(D[n],go(i) + A[n]);
        }
    }
 
    return D[n];
}
 
int main()
{
    cin >> N;
    memset(D, 0, sizeof(D));
    for (int i = 1; i <= N; i++)
    {
        cin >> A[i];
        D[i] = A[i];
        
    }
 
    for (int i = 1; i <=N; i++)
    {
        ans=max(ans,go(i));
    }
 
    cout << ans << endl;
 
    return 0;
}