동적 계획법 - 4. 최대 증가 부분 수열

문제 : 최대 증가 부분 수열 (난이도 下)

 

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

 

 코드

int n;
int cache[101], S[100];
int makeLIS(int start)
{
	int& ret = cache[start + 1];
	if (ret != -1) return ret;
	ret = 1; //최소길이 1
	for (int next = start+1; next < n; next++)
	{
		if (start == -1 || S[start] < S[next])
		{
			ret = max(ret, makeLIS(next) + 1);
		}
	}
	return ret;
}

int main()
{
	int C;
	cin >> C;
	while (C--)
	{
		memset(cache, -1, sizeof(cache));
		cin >> n;
		for (int i = 0; i < n; i++)
		{
			cin >> S[i];
		}
		int ans = makeLIS(-1) - 1;
		cout << ans << '\n';
	}
	return 0;
}