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

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

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

 

접근:

• 기존에는 가장 길이를 반환하는 형태의 재귀함수로 '가장 긴 증가하는 부분 수열'을 구했다면 이번에는 합을 반환하는 형태로 함수를 바꿔주면 된다.

 

코드:

#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;
int N;
int A[1001];
int cache[1001];

// i에서 시작하는 증가수열 중 가장 큰 증가수열의 합을 반환한다
int getMax(int i)
{
	int& ret = cache[i];
	if (ret != -1) return ret;
	// 아니면 계산한다
	ret = A[i];
	for (int j = i + 1; j <= N; j++)
	{
		if (A[i] < A[j])
		{
			ret = max(ret, A[i] + getMax(j));
		}
	}
	return ret;
}

int main()
{
	ios::sync_with_stdio(false);
	memset(cache, -1, sizeof(cache));

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];

	cout << getMax(0);
	return 0;
}