[BOJ/백준] 11053번 - 가장 긴 증가하는 부분 수열

가장 긴 증가하는 부분 수열

문제

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

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

 

CODE

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

const int mxN=1e3, mxA=1e3;
int n, a[mxN+1];
int dp[mxA+1];

int main() {
	cin >> n;
	for(int i=0; i<n; ++i) {
		cin >>a[i];
	}
	
	int ans=0;
	
	for(int i=0; i<n; i++) {
		dp[i] = 1;
		for(int j=0; j<n; j++) {
			if(a[i]>a[j]) {
				dp[i] = max(dp[i], dp[j]+1);
			}
		}
		ans = max(dp[i], ans);
	}
	cout << ans;
}

 

 

점화식

if(a[i]>a[j]) {
	dp[i] = max(dp[i], dp[j]+1);
}