Java LIS(최대 부분 증가 수열)

문제

분석

LIS 문제. LIS문제는 dp를 이용해서 풀 수 있다. 이때 dp[i]에 무엇을 저장할 것인지가 중요하다.

dp[i]: i번째 요소를 마지막으로하는 최대 증가 수열의 길이.

 

dp[0]을 생각해보자. dp[0]은 0번째 요소를 마지막으로하는 최대 증가 수열의 길이를 저장해야 한다. 그러면 직관적으로 1이라는 것을 알 수 있다. dp[0]은 항상 1이기 때문에 초기화를 해줘야 한다.

 

dp[1]은 1번째 요소를 마지막으로하는 최대 증가 수열의 길이를 저장해야한다. arr[0]이 5이고, arr[1]이 3이므로 최대로 만들 수 있는 길이는 1이다.

 

dp2[]는 2번째 요소를 마지막으로하는 최대 증가 수열의 길이를 저장해야 한다. {5,7}, {3,7}이 있으므로 dp[2]는 2가 된다. 이런식으로 구하면 arr과 dp는 다음과 같이 되고 LIS의 길이는 4가 된다.

 

 

핵심은 dp 요소값을 구할 수 있느냐다.

dp[i]를 구하는 로직을 일반화하면 아래와 같다.

 

• dp[0]은 구했으니 for 1<=i<arr.len 반복
  • 최대값을 저장할 max 선언
  • for(0<=j<i)
    • 앞 부분 값들 중에서 현재 값보다 작고, dp[j]> max 이면 max = dp[j]
  • dp[i] = max + 1

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 최대부분증가수열 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int answer = 1;

        int[] dp = new int[arr.length];
        dp[0] = 1;

        for (int i=1; i<arr.length; i++) {
            int max = 0;
            for (int j=0; j<i; j++) {
                if (arr[j] < arr[i] && dp[j] > max) max = dp[j];
            }
            dp[i] = max + 1;
            answer = Math.max(answer, dp[i]);
        }

        System.out.println(answer);
    }
}