[BOJ/11055/C++] 가장 큰 증가하는 부분 수열

 

이번에 푼 문제는 dp를 이용해서 푸는 문제였다.

 

예를 들어 수열 A에서 3번 째에 있는 수가 1번 째, 2번 째에 있는 수보다 크면 3번 째까지 증가하는 부분 수열의 합을 dp 배열에 저장해놓는 방식이다.

 

그러면 배열 dp에서 오름차순으로 정렬을 했을 때 제일 오른쪽에 있는 수가 최댓값이 될 것이다.

#include<iostream>
#include<algorithm>
using namespace std;
int main(void)
{
	int N;
	cin >> N;

	int A[1001];
	int dp[1001];

	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		dp[i] = A[i] = tmp;
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (A[j] < A[i]) {
				dp[i] = max(dp[i], dp[j] + A[i]);
			}
		}
	}

	sort(dp, dp + N);
	cout << dp[N - 1];

	return 0;
}