(c++)백준 11055번: 가장 큰 증가 부분 수열

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

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

이 문제는 앞에서부터 dp배열을 채웠다.

가장 긴 증가하는 수열문제와 비슷하게 현재 인덱스보다 앞부분을 보면서 값이 더 작고 dp가 제일 큰 것을 저장한 후, 현재 dp에 더하면 된다.

2020/06/09 - [백준/DP] - (c++)백준 11053번: 가장 긴 증가하는 부분 수열

#include <iostream>
using namespace std;

int N;
int A[1001];
long long dp[1001];

void DP() {
	long long Max = -1;

	//앞에서부터
	for (int i = 2; i <= N; i++) {
		int maxSum = 0;
		for (int j = i - 1; j >= 1; j--) {
			if (A[i] > A[j] && dp[j] > maxSum)
				maxSum = dp[j];
		}
		dp[i] += maxSum;
	}

	for (int i = 1; i <= N; i++) {
		if (Max < dp[i])
			Max = dp[i];
	}

	cout << Max << endl;
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		dp[i] = A[i];//dp도 같이 초기화
	}
	DP();
	return 0;
}