300. Longest Increasing Subsequence - cocoder39/coco39_LC GitHub Wiki

300. Longest Increasing Subsequence

Method 1: LIS[i] is the length of longest increasing subsequence ending at nums[i], time complexity is O(n^2)

int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        if(len == 0){
            return 0;
        }
        vector<int> LIS(len, 1);
        LIS[0]  = 1;
        
        for(int i = 1; i < len; i++){
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i] && LIS[i] < LIS[j] + 1){
                    LIS[i] = LIS[j] + 1;
                }
            }
        }
        
        return *max_element(LIS.begin() , LIS.end());
    }

Method 2 : time complexity is O(n * log n)

std::lower_bound assumes the input array is sorted and returns the iterator points to the first element which is not less than (>=) num based on binary search

supposing nums is [1, 6, 8, 5, 7, 9] the sequence would be

1: 1
2: 1, 6
3: 1, 6, 8
4: 1, 5, 8
5: 1, 5, 7
6: 1, 5, 7, 9

step 3 to step 4 is confusing where 6 is replaced by 5. The process would be like follows: at step 3, the LIS1 is 1, 6, 8. at step 4, a new candidate LIS2 generated, LIS2 is 1, 5. Then the LIS is 1, 6, 8 whose length is same as 1, 5, 8 . In other 1, 5, 8 is not the LIS but it maintains the length of LIS. Meanwhile it is open to new elements which can contribute to LIS in the future.

tips:

  • if new element is smaller to existing element, replacing the existing element won't change the length of LIS
  • if new element is equal to existing element, replacing the existing element prevents duplication. duplication is not allowed in LIS
  • if new element is greatest, push it back, increasing the length of LIS.
int lengthOfLIS(vector<int>& nums) {
        vector<int> LIS;
        for (auto num : nums) {
            auto it = lower_bound(LIS.begin(), LIS.end(), num);
            if (it == LIS.end())   LIS.push_back(num);
            else                   *it = num;
        }
        return LIS.size();
    }

follow up: return the sequence

(1)based on solution1, traversal the dp vector from back to the begin, the greatest dp is the end of sequence. then find out the last but one element, whose dp is last_dp - 1 and corresponding value is less than last element. time complexity is still O(n ^ 2)

based on solution 2, we can get the position where the new element should be inserted into. thus we know the dp value of each number in O(n log n) time and O(n) extra memory. then we can follow idea in (1). final time complexity is O(n log n)

second round

int lengthOfLIS(vector<int>& nums) {
        vector<int> LIS;
        int sz = nums.size();
        for (int i = 0; i < sz; i++) {
            if (LIS.empty() || nums[i] > LIS.back()) {
                LIS.push_back(nums[i]);
            } else if (nums[i] == LIS.back()) {
                continue;
            } else { // nums[i] < LIS.back()
                int sz1 = LIS.size(), start = 0, end = sz1 - 1;
                while (start + 1 < end) {
                    int mid = start + (end - start) / 2;
                    if (LIS[mid] < nums[i]) {
                        start = mid;
                    } else {
                        end = mid;
                    }
                }
                
                if (LIS[start] >= nums[i]) { //ATTENTION: if >, [4, 10] 4 => [4, 4]
                    LIS[start] = nums[i];
                } else {
                    LIS[end] = nums[i];
                }
            }
        }
        return LIS.size();
    }
⚠️ **GitHub.com Fallback** ⚠️