LIS 최대 부분 증가수열 - DP

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	vector<int> arr(n+1), dy(n+1);
	
	dy[0]=1;
	dy[1]=1;
	
	for(int i=1; i<=n; i++){
		cin>> arr[i];
	}
	for(int i=2; i<=n; i++){
		int maxx = 0;
		for(int j=i-1; j>=1; j--){
			if(arr[j]<arr[i]){
				maxx = max(dy[j], maxx);
			}
		}
		dy[i] = maxx+1;
	}
	
	int ans=0;
	
	for(int i=1; i<=n;i++){
		ans = max(ans, dy[i]);
	}
	
	cout << ans;
	
	
	
}