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

문제

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

11053번: 가장 긴 증가하는 부분 수열

풀이

dp[i] = i 번째 원소를 마지막으로 하는 LIS의 길이

dp[i] = 1 ~ i - 1까지의 원소들에서, i번째 원소보다 값이 작은것들 중, 가장 큰 dp값 + 1

 

예를 들어 다음과 같이 배열이 있다고 해보자

10

20

10

30

20

50

인덱스 0 부터 시작한다 해보자

dp[0] = 1이다.

dp[1] 은 2이다. 

dp[2]는 1이다. arr[3] 이전의 원소들 중 10보다 작은 원소들이 없다. 따라서 그냥 1이 된다.

이를 계속 하다보면 dp 배열은 다음이 될것이다.

1

2

1

3

2

4

코드

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

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		
		int arr [] = new int [n+1];
		int dp[] = new int[n+1];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		
		int ans = 0;
		
		for(int i=0;i<n;i++) {
			int length = 0;
			for(int j=0;j<i;j++) {
				if(arr[i] > arr[j]) {
					length = Math.max(dp[j], length);
				}
			}
			dp[i] = length+1;
			ans = Math.max(ans, dp[i]);
		}
		
		System.out.print(ans);
	}

    
}