300. Longest Increasing Subsequence -M !!!!!!!!!!!!!!!

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

 

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?

A:

每加入一个数字 val 。查看前面的所有的值。O（n^2)   如果< val ，则其可能是小于的一个。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> Count(n,0);// at each index, ending here, how many LIS can have
        
        int res =0;
        for(int i =0;i<n;++i)
        {
            int preCount =0;
            for(int j=0;j<i;++j)
            {
                if(nums[j]<nums[i])
                {
                    preCount = max(preCount, Count[j]);
                }
            }
            Count[i] = 1 + preCount;
            res = max(res, Count[i]);
        }
        return res;
    }
};

------------第二遍。DP， 每次保存迄今为止，到每个位置的最小的数字。

aka, V[i]表示在 长度为i+1的Longest Increasing Subsequence的可能的最小的值

单调递增堆栈。  
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> V{INT_MIN};
        for(auto num : nums){
            // first compare with the back
            if(num > V.back()){
                V.push_back(num);
            }else{
                for(int i = V.size()-1; i>0;i--){
                    if(num < V[i] && num > V[i-1]){
                        V[i] = num;
                    }
                }
            }
        }
        return V.size()-1;
    }
};
Mistakes：
    在上面第二个if以后，不能break ， 要继续修改。

---------------上面没有利用前面排好序. 而且也只需要更改一个即可。 因此用一个数组V，保存其迄今为止发现的每个长度的结尾最小的可能的值（那么这个数列肯定是递增的）

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // save the record that: for length of k(use index +1), the  minimum ending Value 
        vector<int> vec;
        for(auto val : nums)
        {   // binary search to find the first index bigger than k (may exceed )
            int low = 0, high = vec.size();
            while(low<high)
            {
                int mid = low+ (high - low)/2;
                if(vec[mid] >= val) // here, >= is the key.  (previous, I choose >)
                {
                    high = mid;
                }else{
                    low = mid+1;
                }
            }
            if(low >= vec.size()) // failed to find an ending value bigger than current
            {
                vec.push_back(val);
            }else{
                vec[low] = val;
            }
        }
        return vec.size();
    }
};