[디폴트 코드] LIS 최장 증가 부분수열

최장 증가 부분 수열

• 2중 for 문으로 구성
• dp배열에는 현재 위치 인덱스 까지 최장 증가 부분수열

  배열의 값이 자신보다 값이 작으면 해당 위치 인덱스의 최장 증가 부분 수열보다 하나 더 길다.
  2중 for문 돌면서 갱신 해주면 된다.

• 다른 어려운 DP에도 응용해서 사용한다. 이것 때문에 기억해두어야 할 듯

예제

public class J08_가장긴증가하는부분수열_LIS {

	static BufferedWriter bw;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		//
		// 가장 긴 증가하는 부분 수열
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int[] dp = new int[N];
		int answer = 0;
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		dp[0] = 1;
		for (int i = 1; i < dp.length; i++) {
			dp[i] = 1;
			for (int j = 0; j < i; j++) {
				if ( arr[j] < arr[i] ) {
					dp[i] = Math.max(dp[j] + 1, dp[i]);
				}
			}
			answer = Math.max(answer, dp[i]);
		}
        
		bw.append(answer+"");
		bw.flush();
		bw.close();
		br.close();
		
		
	}
	
}