leetcode 300. Longest Increasing Subsequence

原题传送门->300. Longest Increasing Subsequence

Description:

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
-1e4 <= nums[i] <= 1e4

解法1：标准dp

class Solution {
public:
    int * dp;
    int lengthOfLIS(vector<int>& nums) {
        dp = new int[nums.size()];
        memset(dp,0,nums.size()*4);
        for(int i = 0; i < nums.size(); ++i){
            for(int j = i-1; j >= 0; --j){
                if((nums[i] > nums[j])&&(dp[i]<(dp[j]+1)))
                dp[i] = dp[j]+1;
            }
        }
        int ans = 0;
        for(int i = 0; i < nums.size(); ++i){
            if(dp[i] > ans) ans = dp[i];
        }
        delete []dp;
        return ans+1;
    }
};

时间复杂度O(N^2)

解法2：dp优化

前面的dp，dp[i]的过程可以进一步优化。

参考解法:
最长上升子序列（动态规划 + 二分查找，清晰图解）

但是细节真的很多。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int>dp;
        vector<int>tails;
        dp.resize(nums.size());
        tails.resize(nums.size()+1);
        int ans = 0;
        for(int i = 0; i < nums.size(); ++i){
            int k = binaSearch(tails,1,ans,nums[i]);
            if(k == -1){
                dp[i] = 1;
                tails[1] = nums[i];
            }
            else {
                dp[i] = k+1;
                tails[k+1] = nums[i];
            }
            if(dp[i] > ans) ans = dp[i];
        }
        return ans;
    }
    int binaSearch(vector<int>& tails,int left, int right, int target){//找到比target小的最大值
        int l = left, r = right;
        int mid;
        while(l <= r){
            mid = l+ (r-l)/2;
            if(tails[mid] >= target){ //WA点1：一开始用的大于号
                r = mid-1;
                continue;
            }
            if(tails[mid] < target){
                if((mid == right)||(tails[mid+1] >= target))//WA点2
                return mid;
                l = mid+1;
                continue;
            }
            return mid;
        }
        return -1;
    }
};

注意WA点2:我一开始判越界是写的:if(mid == tails.size()-1)emmm..细节真的太糙了。