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

문제 출처

1. 구상

• 수열을 저장하는 배열 만들기

• 길이를 저장하는 배열 만들기

• 현재 값보다 바로 전 값이 작으면 현재 값의 위치의 길이와 재귀호출을 한 전 값 + 1 중 큰 값을 길이 배열에 저장
  (LIS 알고리즘)
  
  

2. 구현

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

public  class Main {
	
	public static int[] dp;
	public static int[] arr;
	
	public static void main(String[] args) throws Exception {
		Scanner s = new Scanner(System.in);
		
		int total = s.nextInt();
		dp = new int[total];
		arr = new int[total];	
		
		for (int i = 0; i < total; i++)
			arr[i] = s.nextInt();
		
		
		for(int i = 0; i < total; i++)
			LIS(i);
		
		int max = dp[0];
		
		for (int i = 1; i < total; i++) {
			max = Math.max(max, dp[i]);
		}
		
		System.out.println(max);
		
				
	}
	
	public static int LIS(int a) {
		//탐색했는지 확인하기
		if (dp[a] == 0)  {
			dp[a] = 1;
			
			for(int i = a - 1; i >= 0; i--) {
				if(arr[i] < arr[a])
					dp[a] = Math.max(dp[a], LIS(i) + 1);
			}
			
		}	
		
		return dp[a];
		
		}
	
	
} 

코드 및 알고리즘 참고 링크

- LIS 알고리즘 이용.

- 전 값과 현재 값을 비교하여 길이 저장.