[백준 11055번] 가장 큰 증가 부분 수열 (C++)

문제링크 : https://www.acmicpc.net/problem/11055

 

#include <bits/stdc++.h> 
using namespace std;

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

int main()
{
	cin >> n;
	for (int i = 1; i <=n; i++)
	{
		cin >> arr[i];      
		dp[i] = arr[i];
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j < i; j++)    
		{
			if (arr[i] > arr[j])  //arr[1 ~ i-1]까지 값 중에 arr[i]보다 작은 값이 있는지 확인
			{
				dp[i] = max(dp[i], dp[j] + arr[i]); //dp 값을 현재 값과 조건을 만족하는 그전의 값의 합으로 갱신                    
			}
		}
	}
	sort(dp, dp + 1001);
	cout << dp[1000];
}

[백준 11722번] 가장 긴 감소하는 부분 수열 문제에서 조건만 반대로 하고 dp 식을 합을 저장하도록 수정했다.