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

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

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

 

dp[i]는 입력받은 i번째 항을 포함하는 i번째 항까지의 증가 부분 수열의 최댓값 입니다.

10 1 100 2 50 60 3 5 6 7 8

다음 예시에서

1번째항을 포함하는 1번째 항까지의 최댓값의 증가 부분 수열은 10 --> dp[1] = 10

2번째항을 포함하는 2번째 항까지의 최댓값의 증가 부분 수열은 1 --> dp[2] = 1

3번째항을 포함하는 3번째 항까지의 최댓값의 증가 부분 수열은 1 100 --> dp[3] = 101

4번째항을 포함하는 4번째 항까지의 최댓값의 증가 부분 수열은 1 2 --> dp[4] = 3

...

즉, dp[i] = max(현재 항 + dp[(i-1)...0]) 입니다.

이 때, 증가 부분 수열이므로, 현재 항이 dp[(i-1)...0] 보다 클 때만 값을 업데이트 해주었습니다.

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int n, a[1001], dp[1001] = { 0 }, s;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	s = dp[1] = a[1];
	for (int i = 2; i <= n; i++) {
		for (int j = i-1; j >= 0; j--)
			if (a[j] < a[i]) dp[i] = max(dp[i], a[i] + dp[j]);
		s = max(dp[i], s);
	}
	printf("%d", s);
}