[백준] 11053 가장 긴 증가하는 부분 수열 [자바]

 

---

https://st-lab.tistory.com/137

[백준] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA [자바]

https://chanhuiseok.github.io/posts/algo-49/

알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘

 

---

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

public class Main {
	static int[] series;
	static Integer[] dp;
	static int[] len;
	static int N;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		series = new int[N+1];
		dp = new Integer[N+1];
		len = new int[N+1];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i = 1; i <= N; i++) {
			series[i] = Integer.parseInt(st.nextToken());
		}
		for(int i = 1; i <= N; i++) {
			recur(i);
		}
		dp[0] = 0;
		Arrays.sort(dp);
		System.out.println(dp[N]);
	}
	static int recur(int n) {
		if(dp[n] == null) {
			dp[n] = 1;
		
		for(int i = n-1; i>=1; i--) {
			if(series[i] < series[n]) {
			dp[n] = Math.max(dp[n], recur(i)+1);
			}
		}
		}
		return dp[n];
	}
}