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

[문제 링크]

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

---

변형된 LIS문제였다.

 

필자는 길이가 i인 수열에서 i번째 원소를 반드시 포함할 때 갖는 최대값을 memo[i]에 저장하였다.

수열의 길이 N을 입력받았다면 1~N까지 위 작업을 진행한 다음 memo[1]~memo[N]에서 가장 큰 값을 찾아주면 원하는 정답을 얻을 수 있다.

---

#include <iostream>
using namespace std;

int arr[1001], memo[1001];

int max(int a, int b) { return a > b ? a : b; }

int Topdown(int N)
{
	if (N == 0) return arr[N];

	int& ret = memo[N];
	if (ret != 0) return ret;
	
	ret = arr[N];

	for (int i = 0; i < N; i++)
		if (arr[i] < arr[N])
			ret = max(ret, Topdown(i) + arr[N]);
	
	return ret;
}

int Bottomup(int N)
{
	int ret = 0;

	for (int i = 0; i < N; i++)
	{
		memo[i] = arr[i];
		for (int j = 0; j < i; j++)
			if (arr[i] > arr[j])
				memo[i] = max(memo[i], memo[j] + arr[i]);
		
		ret = max(ret, memo[i]);
	}

	return ret;
}

int main(void)
{
	int N;
	cin >> N;
	
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	
	//top-down
	int res = 0;
	for(int i=0; i<N; i++)
		res = max(res, Topdown(i));
	cout << res << endl;

	//bottom-up
	cout << Bottomup(N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 79 day