백준 11053 - 가장 긴 증가하는 부분 수열 (java)

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

배열이 주어지면 값이 증가하는 가장 긴 부분을 찾으면 되는 문제이다.

[10, 20, 10, 30, 20, 50]의 경우 10 20 30 50 의 원소만 체크하면 증가하는 형태이고 길이는 4이기 때문에 예제 출력이 4가 되는 것이다.

배열의 각 인덱스를 돌고 만약 해당 인덱스의 값보다 작은 값이 그 전 인덱스에 있는지 확인을 하고, 작은 값이 있다면 LIS 함수를 호출해 그 인덱스까지의 수열의 길이를 체크하면 된다.

public class Main {  
  
static int[] arr;  
static Integer[] dp;  
  
	public static void main(String[] args) throws Exception {  
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
		StringTokenizer st;  
		StringBuilder sb = new StringBuilder();  
  
		int N = Integer.parseInt(br.readLine());  
  
		arr = new int[N];  
		dp = new Integer[N];  
  
		st = new StringTokenizer(br.readLine());  
		for (int i = 0; i < N; i++) {  
			arr[i] = Integer.parseInt(st.nextToken());  
		}		  
  
		for (int i = 0; i < N; i++) {  
			LIS(i);  
		}  
  
		int max = dp[0];  
  
		for (int i = 1; i < N; i++)  
		{	  
			max = Math.max(max, dp[i]);  
		}  
		System.out.println(max);  
	}  
  
	static int LIS(int N)  
	{  
		if(dp[N] == null){  
			dp[N] = 1;  
  
			for(int i = N - 1; i >= 0; i--)  
			{  
				if(arr[i] < arr[N]){  
					dp[N] = Math.max(dp[N], LIS(i) + 1);  
				}  
			}  
		}  
		return dp[N];  
	}  
}