[LeetCode] 300. Longest Increasing Subsequence

[frdmu]

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

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

 

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
   

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?
 
 
 
解法一：
动态规划。dp[i]表示以nums[i]结尾的最长递增子序列的长度。时间复杂度是0(n^2)代码如下：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        int res = 1;        
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) 
                    dp[i] = max(dp[i], dp[j]+1);                    
            }                  
        } 
        for (int i = 0; i < n; i++) {
            res = max(res, dp[i]);                
        } 
                
        return res; 
    }
};

解法二：
二分法+打牌。代码如下：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> tmp(n, 0);
        int heapno = 0;

        for (int i = 0; i < n; i++) {
            int left = 0, right = heapno;
            int target = nums[i]; 
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] == target) {
                    right = mid;
                } else if (nums[mid] < target) {
                    left = mid + 1;    
                } else {
                    right = mid;
                }   
            }
            if (left == heapno) heapno++;
            nums[left] = target;
        }

        return heapno;
    }
};

Refer:
动态规划设计：最长递增子序列