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

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

LIS 변형 문제이다.

LIS는 DP 배열에 증가 부분 수열의 길이를 갱신하는 반면

이 문제는 같은 증가 부분 수열 내의 원소들의 합을 갱신시키고

각 증가 수열이 끝날 때마다 최댓값을 갱신시켜준 뒤 최종 최댓값을 출력시키면 된다.

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int N, Max = -1;
	int A[1001], dp[1001];
	cin >> N;
	for (int n = 0; n < N; n++) {
		cin >> A[n];
		dp[n] = A[n];
	}
	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]);
		}
		Max = max(Max, dp[i]);
	}
	cout << Max;
	return 0;
}