[백준] 11053번 가장 긴 증가하는 부분 수열 (LIS)

단계별로 풀어보기 동적 계획법 1의 11단계 문제

LIS(Longest Increasing Subsequence) 문제이다.

11053번: 가장 긴 증가하는 부분 수열

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int* numbers = new int[n];
	int* dp = new int[n]; //i까지의 최장 증가하는 수열의 길이를 저장하는 배열
	for (int i = 0; i < n; i++) {
		cin >> numbers[i];
	}
	dp[0] = 0;
	for (int i = 0; i < n; i++) {
		int maxBeforeI = 0; //i 전까지 최장 증가하는 수열의 길이를 저장할 변수
		for (int j = 0; j < i; j++) { //i 전까지
			if (numbers[i] > numbers[j]) { //'증가하는' 조건을 만족하면서
				if (dp[j] > maxBeforeI) //더 긴 수열이 발견되면
					maxBeforeI = dp[j]; //업데이트
			}
		}
		dp[i] = maxBeforeI + 1; // i 전까지를 구했으니까 나 자신 i를 더해줘야 한다.
	}
	int maxDp = 0;
	for (int i = 0; i < n; i++) {
		if (dp[i] > maxDp)
			maxDp = dp[i];
	}
	cout << maxDp << endl;
	return 0;
}

동적 계획법의 특징 답게 특별한 계산 없이 해를 구할 수 있다.

나보다 작으면서 나보다 이전에 있는 LIS에 1만 더해주면 된다.