DP 문제였는데, 풀면서 느끼지만 항상 반례를 잘 만드는게 중요한 것 같고 돌리기 전에 한 번 내가 만든 반례가 잘 돌아가는지 확인하고 돌리자.
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int arr[1001];
int dp[1001] = {0};
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> arr[i];
dp[1] = 1;
for (int i = 2; i <= n; i++)
{
int MAX = 0;
for (int j = i - 1; j >= 1; j--)
{
if (arr[j] < arr[i])
{
MAX = max(MAX, dp[j]);
}
}
dp[i] = MAX + 1;
}
sort(dp + 1, dp + n + 1);
cout << dp[n] << endl;
return 0;
}