[백준] 11568번 민균이의 계략

11053번 문제와 정확하게 일치하는 LIS(Longest Increasing Subsequence) 문제이다.

11568번: 민균이의 계략

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int* card = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> card[i];
	}
	int* lis = new int[n];
	lis[0] = 0;
	int maxLength = 0;
	for (int i = 0; i < n; i++) {
		int longestLengthBeforeI = 0;
		for (int j = 0; j < i; j++) {
			if (card[i] > card[j]) {
				if (lis[j] > longestLengthBeforeI)
					longestLengthBeforeI = lis[j];
			}
		}
		lis[i] = longestLengthBeforeI + 1;
		if (lis[i] > maxLength)
			maxLength = lis[i];
	}
	cout << maxLength << endl;
	return 0;
}