11055번: 가장 큰 증가 부분 수열

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


$O(n)$

dp[i]=max(dp[j] : a[i]>a[j])+a[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]) + a[i]);
    }
    printf("%d", *max_element(dp, dp + n + 1));
    return 0;
}