[BOJ] 11055번 가장 큰 증가 부분 수열

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

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

11053번 가장 긴 증가하는 부분 수열과 비슷한 문제

 

아이디어

1,  dp의 개념으로 시간 복잡도 O(n^2)로 풀이가 가능

 

2, , 해당 배열의 숫자를 왼쪽부터 오른쪽으로 순회를 하면서 dp배열에 해당 숫자를 끝으로 증가하는 부분 수열을 만들었을 때 합의 최댓값을 누적하여 저장한다.

 

예시

5번째의 숫자까지의 증가하는 부분 수열로 만들 수 있는 합의 최대값을 구하고자 한다면 0~4까지의 5번째 숫자보다 작은 숫자들에 대하여 dp의 값을 순회를 한 다음 그중에서 dp값이 가장 큰 값을 구하고 그 이후에 5번째 숫자의 값을 더해주면 그 값이 합의 최댓값이다.

 

소스코드

#include<cstdio>
using namespace std;

int num_arr[1001];
int dp[1001]; //앞부터 조사했을 때의 합의 최대값들을 누적하여 저장

int main()
{
	int a;
	int res = -1;
	scanf("%d", &a);

	for (int i = 0; i < a; i++) {
		scanf("%d", &num_arr[i]);
	}

	for (int i = 0; i < a; i++) {
		int max_amount = 0;

		for (int j = 0; j < i; j++) {
			if (num_arr[j] < num_arr[i]) {
				if (max_amount < dp[j]) {
					max_amount = dp[j];
				}
			}
		}

		//최종적으로 조사하는 인덱스에서 가질수 있는 최대의 값 저장
		dp[i] = max_amount + num_arr[i];

		if (res < dp[i]) res = dp[i];
	}

	printf("%d\n", res);

	return 0;
}