DP #11053: 가장 긴 증가하는 부분 수열 [JAVA]

https://www.acmicpc.net/problem/11053

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

 

 

 

 

---

 

 

 

 

문제 접근

 

 

 

 

이 문제는 알고리즘 문제 중 유명한 유형인 LIS(최장 증가 부분 수열, Longest Increasing Subsequence)라고 한다.

 

 

LIS는 앞에서부터 뒤로 숫자를 선택해서 부분 수열을 구성해 나갈 때 증가하는 순서대로 숫자를 선택하면서(앞에 고른 수보다 뒤에 고른 수가 더 커야함.) 선택한 부분 수열의 길이가 최대가 되도록 하는 경우이다.

 

 

 

 

 

 

[ 참고] https://st-lab.tistory.com/137

 

 

dp[i] : seq[i]를 포함한 가장 긴 증가하는 부분 수열의 길이

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

 

 

 

 

 

top down - 재귀

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static Integer[] dp;
	static int[] seq;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		seq = new int[N];
		dp = new Integer[N];

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			seq[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 0; i < N; i++) {
			recur(i);
		}

		int max = dp[0];

		for (int i = 1; i < N; i++) {
			if (max < dp[i]) {
				max = dp[i];
			}
		}

		System.out.println(max);

	}

	static int recur(int n) {

		if (dp[n] == null) {

			dp[n] = 1;

			for (int i = n - 1; i >= 0; i--) {
				if (seq[i] < seq[n]) {
					dp[n] = Math.max(dp[n], recur(i) + 1);
				}
			}
		}

		return dp[n];

	}

}