300. Longest Increasing Subsequence

문제: leetcode.com/problems/longest-increasing-subsequence/

Longest Increasing Subsequence - LeetCode

 

 LIS 문제인데 O(nlogn) 해답이 재밌다.

 처음에는 각 요소별로 재귀 진입해서 LIS를 하되 cache로 memoization을 해주는 O(N^2) 정도가 직관적으로 떠오른다.  더 최적화하면 LIS를 additional space에 만들고 해당 space는 정렬되어있으므로 binary search로 현재 값이 들어갈 공간을 찾아서 initialize한다.  이렇게하면 주어진 vector를 선형 탐색하면서 binary search를 하니 O(nlogn)이 걸린다.

 

class Solution {
public:
    vector<int> cache;
    int binarySearch(vector<int> array, int target){
        int left = 0;
        int right = array.size() - 1;
        if(array.empty() || array[right] < target){
            return -1;
        }
        
        while(left < right){
            int mid = left + (right - left) / 2;
            
            if(array[mid] < target){
                left = mid + 1;
            } else if(array[mid] == target){
                return mid;
            } else if(array[mid] > target){
                right = mid;
            }
        }
        return left;
    }
    
    int lengthOfLIS(vector<int>& nums) {
        int ans = 0;
        vector<int> array;
        
        for(int i = 0; i < nums.size(); i++){
            int ret = binarySearch(array, nums[i]);
            if(ret == -1){
                array.push_back(nums[i]);
            } else {
                array[ret] = nums[i];
            }
        }
        return array.size();
    }
};

 binary search에서는 현재 값보다 상대적으로 큰 수 중 가장 작은 값을 찾아야한다.  LIS의 특성을 이용하는 것이다.  

 

Example explanation

 문제의 첫 번째 예시인 [10,9,2,5,3,7,101,18]를 기준으로 설명한다.  현재 값보다 상대적으로 큰 수 중 가장 작은 값을 찾아서 바꿔준다.  [10, 9, 2] 부분집합을 보면 10과 9의 뒤에 오는 LIS는 2의 부분집합이므로 2를 선택한다.  [5, 3]의 부분집합을 보면 5의 뒤에 오는 LIS는 3의 뒤에 오는 LIS의 부분집합이므로 3을 선택한다.  이런식으로 주어진 vector를 모두 순회하며 적용하면 전체 배열에 대한 가장 긴 증가하는 수열이 나온다.