백준 - 11053번 - 가장 긴 증가하는 부분 수열

11053번

import java.io.*;
import java.util.*;

public class Main {

	static Integer dp[];
	static Integer arr[];

	static int LIS(int N) {

		// 만약 탐색하지 않던 위치의 경우
		if(dp[N] == null) {
			dp[N] = 1;	// 1로 초기화

			// N 이전의 노드들을 탐색
			for(int i = N - 1; i >= 0; i--) {
				// 이전의 노드 중 seq[N]의 값보다 작은 걸 발견했을 경우
				if(arr[i] < arr[N]) {
					dp[N] = Math.max(dp[N], LIS(i) + 1);
				}
			}
		}
		return dp[N];
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int num = Integer.parseInt(bf.readLine());

		st = new StringTokenizer(bf.readLine());
		dp = new Integer[num];
		arr = new Integer[num];
		for (int i = 0; i<num; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		// 0 ~ N-1 까지 탐색
		for(int i = 0; i < num; i++) {
			LIS(i);
		}

		int max = dp[0];
		// 최댓값 찾기
		for(int i = 1; i < num; i++) {
			max = Math.max(max, dp[i]);
		}
		System.out.println(max);

	}

}

풀이

점화식...
배열에 뭘 담을지 생각해
다 구하고 최댓값을 찾아도 돼
재귀 메서드에 for문을 넣어도 돼