[백준 17216] 가장 큰 감소 부분 수열 (C++)

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

문제

---

수열 A가 주어졌을 때, 그 수열의 감소 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5} 인 경우에 합이 가장 큰 감소 부분 수열은 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5} 이고, 합은 186이다.

 

입력

---

 첫째 줄에 수열 A의 크기 N(1 ≤ N ≤ 1000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 A_i가 주어진다.(1 ≤ A_i ≤ 1,000)

 

출력

---

첫째 줄에 수열 A의 합이 가장 큰 감소 부분 수열의 합을 출력한다.

 

문제 풀이

---

LIS 알고리즘.

일반적인 LIS 알고리즘에서는 dp 배열에 증가하는 형태이면서/ 혹은 감소하는 형태이면서 i번째 원소를 포함한 부분 수열의 최대 길이를 저장했다면, 이 문제는 감소 부분 수열의 가장 큰 합을 구해주면 된다.

첫번째는 첫번째 원소까지의 감소 부분 수열의 최대 합은 arr[0]이다. 이후 i 반복문을 돌면서 첫번째 원소부터 i번째 원소 이전까지 j 반복문을 돈다. j번째 원소가 i번째 원소보다 커야 하며, dp[j]의 값이 가장 커야 해당 부분 수열 뒤에 i번째 원소를 붙여 가장 큰 감소 부분 수열을 만들 수 있다.

모든 원소에 대해 가장 큰 감소 부분 수열의 합을 구했다면 dp 배열 전체를 돌며 가장 큰 값을 찾아 출력하면 된다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	int* arr = new int[N];
	int* dp = new int[N];
	int answer = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	dp[0] = arr[0];
	for (int i = 1; i < N; i++)
	{
		int sum = 0;
		for (int j = 0; j < i; j++)
		{
			if (arr[j] > arr[i] && dp[j] + arr[i] > sum)
			{
				sum = dp[j] + arr[i];
			}
		}
		if (sum == 0)
		{
			dp[i] = arr[i];
		}
		else
		{
			dp[i] = sum;
		}
	}
	for (int i = 0; i < N; i++)
	{
		answer = max(answer, dp[i]);
	}
	cout << answer << "\n";
	return 0;
}