문제

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

예제

---

풀이

https://yabmoons.tistory.com/87
https://ku320121.tistory.com/392

dp[i] = x : 0부터 i번째 인덱스까지, 합이 가장 큰 부분 수열의 합은 x이다.

합이 가장 작은 부분 수열의 합은 다름 아닌 자기 자신인 arr[i]이므로, dp 테이블을 초기화 할 때는 dp[i] = arr[i] 이렇게 하면 된다.

#include <iostream>
#include <vector>
#include <algorithm> 
using namespace std;

int n;
int arr[1001]; 
int dp[1001];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n; 
	
	for(int i = 0; i < n; i++){
		cin >> arr[i];
		dp[i] = arr[i]; // dp 테이블 초기화 
	}

	for(int i = 0; i < n; i++){
		// j = 0 to (i-1)
		for(int j = 0; j < i; j++){
			// 증가하는 부분 수열인지 && 합이 더 커지는지 검사 
			if(arr[j] < arr[i] && dp[i] < dp[j] + arr[i]){
				// 부분 수열의 최대 합 갱신 
				dp[i] = dp[j] + arr[i];
			}
		}
	}

	int ans = 0; 
	for(int i = 0; i < n; i++){
		ans = max(ans, dp[i]); 
	}

	cout << ans; 
	
	return 0;
}