Longest Increasing Subsequence

https://leetcode.com/problems/longest-increasing-subsequence/

Longest Increasing Subsequence - LeetCode

 

배열 내에 값이 증가하는 최대 길이를 찾는 문제이다. 현재 값 보다 이전의 작은 값들일 때의 길이 값을 알면 1을 더하여 현재 최대 가능 길이 값을 구할 수 있다. 이전에 현재 값보다 작은 값이 없다면 1이 된다.

 

DP 배열을 만들어 배열에 길이 값을 저장하여 문제를 풀어주었다. 아래의 코드와 같이 다이나믹 프로그래밍 방식으로 풀어 통과하였다.

public class Solution {  
    public int lengthOfLIS(int[] nums) {  
        int[] dp = new int[nums.length];  
        dp[0] = 1;  
  
        int answer = 1;  
        for(int i = 1; i < nums.length; i++){  
            int num = nums[i];  
            int search = i;  
            dp[i] = 1;  
            while(search-- > 0){  
                int compare = nums[search];  
                if(compare < num){  
                    dp[i] = Math.max(dp[search] + 1, dp[i]);  
                }  
            }  
  
            answer = Math.max(dp[i], answer);  
        }  
  
        return answer;  
    }  
}

 

문제 풀이 후 다른 해답 중에 이진 탐색을 쓰는 경우도 있었다. 숫자 배열을 만들고 정렬하며 현재의 num 값을 삽입해주는 형태였다. 삽입 해주어야 하는 인덱스를 이진 탐색을 이용할 경우 DP로 풀때 O2 의 시간복잡도를 갖지만, 이진탐색의 경우 O(n log(n)) 의 시간복잡도로 더욱 빠르게 해결되는 것으로 확인하였다. 아래와 같이 java의 이진 탐색 메서드를 통해 쉽고 더 빠른 구현이 가능하다.

public class Solution {
    public int lengthOfLIS(int[] nums) {            
        int[] dp = new int[nums.length];
        int len = 0;

        for(int x : nums) {
            int i = Arrays.binarySearch(dp, 0, len, x);
            if(i < 0) i = -(i + 1);
            dp[i] = x;
            if(i == len) len++;
        }

        return len;
    }
}