11053번: 가장 긴 증가하는 부분 수열

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


$O(n^2)$

최장증가수열을 구하는 문제이다. nlgn 해법도 있다.
dp[0]=1
dp[n]= a[n]>a[i]인 i 중 max(dp[i])+1

답은 max(dp[i])

#include<cstdio>
#include<algorithm>
using namespace std;
int n, a[1001], dp[1001];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        for (int j = 0; j < i; j++) dp[i] = max(dp[i], dp[j] * (a[i]>a[j]) + 1);
    }
    printf("%d", *max_element(dp, dp + 1 + n));
    return 0;
}