300. Longest Increasing Subsequence

题目

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

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that 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?

题意

找出最长递增子序列的长度.(子序列是不连续的)

分析

直接用了O(n log n) 的方法,
dp[i]表示长度为i+1的递增子序列的最小值.(显然是递增的)
遍历一次数组, 每访问一个a[j], 就去dp那里用二分法找到它所对应的位置i, 如果他比这个dp[i]这个数要小,说明这个长度为i+1的递增子序列的第i个值可以换成这个更小的值(以便之后能放更多的数)描述比较难理解,看个图吧:

边界和特殊情况的处理比较麻烦,我这个代码还不算完善.

代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (!n) return 0;
        vector<int> smallestNumOflen(0);
        for (int i = 0; i < n; i++) {
            int len = find(smallestNumOflen, nums[i]);
            if (len == smallestNumOflen.size() ) {
                if (len > 0 && smallestNumOflen[len-1]==nums[i])
                    continue;
                smallestNumOflen.push_back(nums[i]);
            } else if (smallestNumOflen[len] > nums[i]) {
                if (len > 0 && smallestNumOflen[len-1]==nums[i])
                    continue;
                    smallestNumOflen[len] = nums[i];
            } 
        }
        return smallestNumOflen.size();
    }

    int find(vector<int>&dp, int num) {
        int left = 0, right = dp.size()-1;
        while (left <= right) {
            int mid = (left+right)/2;
            if (dp[mid] > num) {
                right = mid-1;
            } else if (dp[mid] < num) {
                left = mid+1;
            } else {
                return mid+1;
            }
        }
       return left;
    }
};