알고스팟 - 최대 증가 부분 수열 (LIS) [C++]

 이 문제는 다이나믹 프로그래밍을 풀 수 있는 문제이다. 수열 A에 대해 dp[i]를 A[..i] 까지의 LIS로 정의하면, 이중 for문만으로 문제를 해결할 수 있다. 수열의 최대 길이가 500이므로, 시간 안에 충분히 풀 수 있다.

 

#include <iostream>
#include <algorithm>

using namespace std;

#define MAX 500

int arr[MAX];

// dp[i] : arr[..i] 까지의 LIS
int dp[MAX];

void init(int N) {
	for (int i = 0; i < N; i++) {
		dp[i] = 1;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int C;
	cin >> C;

	for (int test = 0; test < C; test++) {
		int N;
		cin >> N;

		init(N);
		for (int i = 0; i < N; i++) {
			cin >> arr[i];
		}

		for (int i = 1; i < N; i++) {
			int temp = 1;

			for (int j = 0; j < i; j++) {
				if (arr[j] < arr[i]) {
					temp = max(temp, dp[j] + 1);
				}
			}

			dp[i] = temp;
		}

		int answer = 0;
		for (int i = 0; i < N; i++) {
			answer = max(answer, dp[i]);
		}

		cout << answer << '\n';
	}

	return 0;
}