Description:

Given a sequence of integers, find the longest increasing subsequence (LIS).

You code should return the length of the LIS.

Example:

For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3
For [4, 2, 4, 5, 3, 7], the LIS is [2, 4, 5, 7], return 4

Link:

http://www.lintcode.com/en/problem/longest-increasing-subsequence/

題目意思：

給一個數(shù)組nums，找出這個數(shù)組中最長的遞增子集的個數(shù)，子集元素在數(shù)組中的順序不能打破。

解題方法：

DP:

1. 創(chuàng)建一個數(shù)組dp，代表數(shù)組中每個元素前面有幾個比它小的元素（遞增），從到到尾遍歷數(shù)組nums，在i位置時，j從i-1到0去查找比nums[i]小的元素，在這些元素中找到對應(yīng)的dp值最大的。狀態(tài)方程為：dp[i] = max(dp[j])+1。
   最后在dp中找到最大值max，并返回max+1。
2. 維護(hù)一個遞增的數(shù)組dp，利用binary search來查找輸入數(shù)組中每個數(shù)在這個數(shù)組中的位置，并且在每次查找后，將查找的數(shù)替換dp中相應(yīng)位置原有的數(shù)（如果查找的index超過dp的長度則在最后則添加在后面）。

Tips:

注意dp數(shù)組僅僅記錄了在某個位置上的元素前面有幾個符合題目標(biāo)準(zhǔn)的數(shù)字，所以最后返回結(jié)果要+1，這才代表子集的個數(shù)。

Time Complexity：

時間O(N^2) 空間O(N)

時間O(NlogN) 空間O(N)

完整代碼：

1.
int longestIncreasingSubsequence(vector<int> nums) 
    {
        if(nums.size() == 0)
            return 0;
        vector <int> dp (nums.size(), 0);
        for(int i = 1; i < nums.size(); i++)
        {
            int max = 0; 
            bool find = false;
            for(int j = i-1; j >= 0; j--)
            {
                if(nums[j] < nums[i])
                {
                    max = dp[j] > max ? dp[j] : max;
                    find = true;
                }
            }
            if(find)
                dp[i] = max+1; //如果沒找到，dp值依然為0
        }
        int max = 0;
        for(int i = 1; i < dp.size(); i++)
            max = dp[i] > max ? dp[i] : max;
        return max+1;
    }
2.
int bs(vector<int>& nums, int n) {
    int len = nums.size();
    if(!len || n < nums[0])
        return 0;
    if(n > nums[len - 1])
        return len;
    int start = 0, end = len - 1;
    while(start + 1 < end) {
        int mid = start + (end - start) / 2;
        if(nums[mid] == n)
            return mid;
        else if(nums[mid] > n)
            end = mid;
        else 
            start = mid;
    }
    if(nums[start] == n)
        return start;
    if(nums[end] == n)
        return end;
    if(nums[start] > n)
        return start;   
    else 
        return end;
}

int LIS(vector<int>& nums) {
    int len = nums.size();
    if(len < 2)
        return len;
    vector<int> DP;
    for(int i: nums) {
        int index = bs(DP, i);
        if(index == DP.size())
            DP.push_back(i);
        else 
            DP[index] = i;
    }
    return DP.size();
}