문제

수열 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의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

풀이

입력을

6
10 90 30 80 40 100

을 가지고 예를 들어보자

dp 배열 초기화는 각 arr의 숫자로 해둔다. 그리고 코딩을 실행하면 다음과 같이 dp가 변화하게 된다.
우선적으로 입력받은 arr 배열을 비교하고 후순위로 dp배열을 비교한다.
dp[i] > dp[j] + arr[i] 이면 해당 인덱스에서 최대 조건을 만족하지 못하므로 무시
dp[i] < dp[j] + arr[i] 이어야 dp[i]가 최대가 되므로 dp[i] = dp[j] + arr[i] 로 수정한다.
100을 기준으로 한번 코딩을 돌려보자.

• 90을 만나면 arr[j] < arr[i] && DP[i](110) < DP[j] + arr[i](200) 조건을 만족. DP[i] = DP[j] + arr[i] 을 실행. -> dp[i] = 200
• 80을 만나면 arr[j] < arr[i] && DP[i](200) < DP[j] + arr[i](220) 조건을 만족. DP[i] = DP[j] + arr[i] 을 실행. -> dp[i] = 220

코드

#include <iostream>
using namespace std;
int DP[1001] = { 0, };

int check_max(int* arr)
{
	int max = arr[1];
	for (int i = 2; i <= 1001; i++)
	{
		if (max < arr[i])
			max = arr[i];
	}
	return (max);
}

int main()
{
	int n;
	int arr[1001];

	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	for (int i = 1; i <= n; 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[j] + arr[i])
				DP[i] = DP[j] + arr[i];
		}
	}
	for (int i = 1; i <= n; i++)
	{
		printf("%d ", DP[i]);
	}
	int max = check_max(DP);
	printf("%d", max);
}