[알고스팟] 최대 증가 부분 수열

링크: https://algospot.com/judge/problem/read/LIS

algospot.com :: LIS

---

동적 계획법으로 풀 수 있는 대표적인 문제입니다. 동적 계획법으로 최적화 문제를 풀때, 다음과 같은 절차를 밟는다고 생각하면 편합니다.

1. 완전 탐색으로 설계
2. (최적 부분 구조) 최적화 문제로 부분문제 변환
3. 메모이제이션 적용

아래 코드들은 다음과 같은 절차에 의해 LIS(Longest Increasing Sequence)를 구합니다.

<파이썬3 소스 코드>

import sys
rl = lambda:sys.stdin.readline()

def lis(idx=0):
    if cache[idx] != -1:
        return cache[idx]
    ret = 1
    for nex in range(idx + 1, length):
        if seq[idx] < seq[nex]:
            ret = max(ret, lis(nex) + 1)
    cache[idx] = ret
    return ret

for _ in range(int(rl())):
    length = int(rl())
    seq = list(map(int, rl().split()))
    cache = [-1 for _ in range(length)]
    MAX = 1
    for i in range(length):
        MAX = max(MAX, lis(i))
    print(MAX)

 

<C++ 소스 코드>

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int LIS(int idx, const int N, const vector<int>& seq, vector<int>& cache)
{
	if (cache[idx] != -1)
		return cache[idx];
	int ret = 1;
	for (int nex = idx + 1; nex < N; nex++)
		if (seq[idx] < seq[nex])
			ret = max<int>(ret, LIS(nex, N, seq, cache) + 1);
	cache[idx] = ret;
	return ret;
}

int main(void)
{
	int T;
	scanf("%d", &T);
	for (int t = 0; t < T; t++)
	{
		int N;
		scanf("%d", &N);
		vector<int> seq;
		vector<int> cache;
		for (int i = 0; i < N; i++)
		{
			int elem;
			scanf("%d", &elem);
			seq.push_back(elem);
			cache.push_back(-1);
		}
		int MAX = 0;
		for (int i = 0; i < N; i++)
			MAX = max<int>(MAX, LIS(i, N, seq, cache));
		printf("%d\n", MAX);
	}

	return 0;
}