https://www.acmicpc.net/problem/11053
dp(i)를 i번째 원소가 포함된, 증가하는 부분 수열의 최대 길이라고 하자.
i번째 원소가 i>j인 j번째 원소보다 크면
dp(i) = dp(j) + 1 이다.
j가 2개 이상일 경우, i보다 작은 여러 j에 대해서
dp(i) = dp(j)의 최댓값 + 1 이다.
그리고 최종 결과는 dp(i)의 최댓값이다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, ans;
cin >> n;
vector<int> v(n);
for(int i=0; i<n; i++){
cin >> v[i];
}
vector<int> dp(n, 1);
if(n == 1) cout << 1;
else {
for(int i=1; i<n; i++){
for(int j=0; j<i; j++){
if(v[i] > v[j]) {
dp[i] = max(dp[i], dp[j]+1);
}
}
}
cout << *max_element(dp.begin(), dp.end());
}
return 0;
}