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

문제

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

풀이

이 문제는 다이나믹 프로그래밍 문제이다.

 

점화식

dp[i] = max(dp[j] + 1, dp[i])

 

여기서 모든 요소들은 자기 자신을 수열에 포함하므로 초기 값을 1 설정한다.

#include <iostream>
#include <vector>

using namespace std;

int dp[1001] = { 0, };
int main() {
	int n;
	cin >> n;

	vector<int> vec(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> vec[i];
		dp[i] = 1;
	}

	int maxCount = 1;
	for (int i = 2; i <= n; i++) {	
		for (int j = i - 1; j >= 1; j--) {
			if (vec[j] < vec[i]) {
				dp[i] = max(dp[j] + 1, dp[i]);
			}
		}

		maxCount = max(dp[i], maxCount);
	}

	cout << maxCount;

	return 0;
}