백준 9177 가장 큰 증가 부분 수열 - C++

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

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

신촌 알고리즘 초급 3주차 문제.

 

DP 중 굉장히 유명한 문제로, 하나의 수열이 주어졌을 때, 그 수열의 부분 수열 중 증가 부분 수열의 성질을 만족하고,

내부 원소들의 합이 가장 큰 수열의 합을 출력한다.

 

DP[x]를 x번째 원소를 가장 큰 원소로 가지는 증가 부분 수열 중 가장 큰 원소합이라고 하면

 

DP[i] (i<x) 를 통해서 DP[x]를 유추할 수 있다. 

만약 A[i] < A[x] 이면, DP[i]에서 구한 증가 부분 수열에 A[x]를 추가해도 부분 수열을 만족하고,

더 큰 원소합을 가질 수 있게 된다. 

 

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <memory.h>


using namespace std;
using ll = long long;

ll input[1010], dp[1010] = { 0, };

int main(void) {

	int n;
	
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%lld", &input[i]);

	// dp[x]는 x번째 원소를 포함하는 가장 큰 부분 수열의 합
	dp[0] = input[0];
	for (int i = 1; i < n; i++) {
		dp[i] = input[i];
		for (int j = 0; j < i; j++) {
			// dp[j] : j번째 원소를 포함하는 가장 큰 부분 수열의 합과 비교해서 업데이트
			if (dp[i] > dp[j])
				dp[i] = max(dp[i], dp[j] + input[i]);
		}
	}

	ll result = 0;

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

	printf("%lld", result);

	return 0;
}