백준] 11055 - 가장 큰 증가 부분 수열

시간 제한 : 1초

메모리 제한 : 256MB

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

소스코드

#include <iostream>
using namespace std;
int main(void)
{
	int max, n, arr[1001] = { 0, }, dp[1001] = { 0, };
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
		dp[i] = arr[i];
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j < i; j++)
			if (arr[j] < arr[i])
				dp[i] = dp[i] < (dp[j] + arr[i]) ? (dp[j] + arr[i]) : dp[i];
	max = -1;
	for (int i = 1; i <= n; i++)
		if (max < dp[i])
			max = dp[i];
	cout << max;
}

Tip

DP로 풀면 되고 아주 간단한 1차원적인 점화식이기 때문에 길게 고민할 필요가 없다.

dp[i] = dp[i] < (dp[j] + arr[i]) ? (dp[j] + arr[i]) : dp[i];

유사한 문제로 백준에서 가장 긴 증가하는 수열(11053), 가장 긴 감소하는 수열(11722) 등이 있다.