가장 긴 증가하는 부분 수열

문제

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

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

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);
}

728x90