300. Longest Increasing Subsequence

문제

Given an integer array nums, return the length of the longest strictly increasing

subsequence

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

• 1 <= nums.length <= 2500
• 104 <= nums[i] <= 104

Solution 1

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 자신을 포함한 최대 길이
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int answer = 1;
        for(int i=1;i<nums.length;i++) {
            for(int j=0;j<i;j++) {
                if(nums[i]>nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            answer = Math.max(answer, dp[i]);
        }

        return answer;
    }
}

dp 배열의 각 인덱스의 값은 nums[i]를 포함해서 만들 수 있는 서브 시퀀스의 최대 길이이다. dp[i]는 j를 돌면서 nums[i]>nums[j]인 경우 기존 dp[i]와 dp[j]+1을 비교해서 큰 값을 업데이트한다.

if(nums[i]>nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }

nums[i]>nums[j]이면 num[j]를 포함해서 만들 수 있는 서브 시퀀스 길이에서 1이 늘어나므로 dp[j]+1와 값을 비교한다.

하지만 시간복잡도는 O(n^2)이므로, 요구 조건 O(nlogn)은 성립하지 못한다.

Solution 2

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> arr = new ArrayList<>();

        for(int num : nums) {
            if(arr.isEmpty() || arr.get(arr.size()-1)<num) {
                arr.add(num);
            }
            else {
                int pos = binarySearch(arr, num);
                arr.set(pos, num);
            }
        }
        return arr.size();
    }

    public int binarySearch(List<Integer> arr, int target) {
        int left = 0; 
        int right = arr.size()-1;

        while(left<=right) {
            int mid = (left+ right)/2;
            if(arr.get(mid) == target) {
                return mid;
            }
            else if(arr.get(mid) <target) {
                left=mid+1;
            }
            else {
                right=mid-1;
            }
        }
        return left;
    }
}

이 풀이를 이해하는 데 시간이 다소 걸렸다. 문제에서 요구하는 것은 최장 증가 부분 수열의 길이이므로, 이 풀이의 결과는 정확하다. 그러나 이 풀이에서 생성된 증가 부분 수열 리스트의 최종 상태는 예상과 다를 수 있다.

 

예를 들어, 입력 [10, 9, 2, 5, 3, 5, 11, 4, 18]에 대해 예상 최종 리스트는 [2, 3, 5, 11, 18]이지만, 이진 탐색을 통해 생성된 최종 리스트는 [2, 3, 4, 11, 18]과 같이 예상과 다르다.

 

이는 이진 탐색을 통해 리스트 내부 요소가 더 작은 값으로 대체되기 때문이며, 길이는 동일하므로 결과는 문제의 요구 사항을 충족한다. 반복문 내 이진 탐색을 수행하므로 시간 복잡도는 O(nlog⁡n)이다.