11055(가장 큰 증가하는 부분 수열)

난이도: 실버 2

 

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

11055번: 가장 큰 증가 부분 수열

 

문제

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

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

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

출력

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

 

 

풀이

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 1001

int N;
int A[MAX];
int dp[MAX];

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

	// 증가하는 부분에서 이전 dp의 max값에 A값을 더함
	// 1 100 2 50 60  3 5  6  7  8
	// 1 101 3 53 113 6 11 17 24 32

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

	int result = 0;
	for (int i = 0; i < N; i++)
	{
		if (result < dp[i])
			result = dp[i];
	}
	cout << result << endl;

}