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

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [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. 

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to 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{nums[0]}; // V[i] records minimum ending value of  length (i+1)
        for(int i =1; i< nums.size(); i++){
            int val = nums[i];
            for(int j = V.size()-1; j>=0;j--){
                if( val > V[j]){ // care only if add at end
                    if(j == V.size()-1){
                        V.push_back(val);
                        break;
                    }
                }else if (val < V[j] ){
                    if(j==0 || val > V[j-1]){
                        V[j] = val;
                        break; // since we only edit once 
                    }
                }
            }
        }
        return V.size();
    }
};

---------------上面没有利用前面排好序. 而且也只需要更改一个即可。 因此用一个数组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();
    }
};