DP_백준_가장 긴 감소하는 부분 수열_11722

이 문제 역시 길이에 대하서 N을 정한다. (단 여기서 의미하는 것은 입력받은 숫자를 마지막으로하는 것)

1. 정의 : dp[N] : value[N]을 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이

2. 점화식 : dp[N] = if(dp[N]<dp[i]) && MAX(dp[i[)+1 (0<=i<N)

3. 초기화 : 코드 참조

#include <iostream>
using namespace std;
 
int main() {
    int count;
    cin >> count;
    int * value = new int[count];
    int * dp = new int[count];
    for (int i = 0; i < count; i++) {
        cin >> value[i];
    }
    dp[0] = 1;
    int result = 1;
    //Initialize
 
    for (int i = 1; i < count; i++) { // i == dp index
        int max = 0;// Big length
        for (int j = 0; j < i; j++) {
            if (max < dp[j] && value[i]<value[j]) {
                max = dp[j];
            }
        }
        dp[i] = max + 1;
        if (result < dp[i]) {
            result = dp[i];
        }
    }
    cout << result << endl;
}