백준 11053

#include <iostream>
#include <algorithm>
using namespace std;

int N;
int DP[1001];
int arr[1001] = { 0, };

int main() {
    cin >> N;
    int max = 0;
    for (int i = 1; i <= N; i++)
        cin >> arr[i];

    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= i; ++j) {
            if(arr[i]>arr[j] && DP[j]+1 > DP[i])
            DP[i] = DP[j] + 1;
        }
        if (max < DP[i]) {
            max = DP[i];
        }
    }

    cout << max;
    return 0;
}

백준 최장 부분증가수열을 구하는 문제이다. 

DP 배열에 하나씩 비교해보면서 값을 넣어주면된다.

DP[10]번째를 구하려면 DP[0~9]까지의 배열과 모두 비교를 해봐야한다.

            if(arr[i]>arr[j] && DP[j]+1 > DP[i])
            DP[i] = DP[j] + 1;

이 두줄이 핵심이다.