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

백준 11055 가장 큰 부분 증가 수열

• https://www.acmicpc.net/problem/11055
• dp[i] : i번째 수를 마지막 원소로 가지는 LIS의 합

#include <iostream>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int dp[1001] = { 0 };
	int A[1001] = { 0 };

	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> A[i];

	int max = A[0];
	dp[0] = A[0];

	for (int i = 1; i < n; i++) {
		dp[i] = A[i];

		for (int j = 0; j < i; j++) 
			if (A[i] > A[j] && dp[j] + A[i] > dp[i])
				dp[i] = dp[j] + A[i];
		if (max < dp[i]) max = dp[i];
	}

	cout << max;
	return 0;
}