lintcode-76-最长上升子序列

76-最长上升子序列

给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。

说明

最长上升子序列的定义：
最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列，这种子序列不一定是连续的或者唯一的。https://en.wikipedia.org/wiki/Longest_increasing_subsequence

样例

给出 [5,4,1,2,3]，LIS 是 [1,2,3]，返回 3
给出 [4,2,4,5,3,7]，LIS 是 [2,4,5,7]，返回 4

挑战

要求时间复杂度为O(n^2) 或者 O(nlogn)

标签

动态规划 LintCode 版权所有二分法

思路

参见博客http://www.cnblogs.com/dartagnan/archive/2011/08/29/2158247.html，利用栈和二分查找。

这个算法其实已经不是DP了，有点像贪心。至于复杂度降低其实是因为这个算法里面用到了二分搜索。本来有N个数要处理是O(n)，每次计算要查找N次还是O(n)，一共就是O(n^2)；现在搜索换成了O(logn)的二分搜索，总的复杂度就变为O(nlogn)了。

这个算法的具体操作如下(by RyanWang):

开一个栈，每次取栈顶元素top和读到的元素temp做比较，如果temp > top 则将temp入栈；如果temp < top则二分查找栈中的比temp大的第1个数，并用temp替换它。最长序列长度即为栈的大小top。
这也是很好理解的，对于x和y，如果x < y且Stack[y] < Stack[x],用Stack[x]替换Stack[y]，此时的最长序列长度没有改变但序列Q的''潜力''增大了。

举例：原序列为1，5，8，3，6，7
栈为1，5，8，此时读到3，用3替换5，得到1，3，8；再读6，用6替换8，得到1，3，6；再读7，得到最终栈为1，3，6，7。最长递增子序列为长度4。

当出现1，5，8，2这种情况时，栈内最后的数是1，2，8不是正确的序列啊？难道错了？
分析一下，我们可以看出，虽然有些时候这样得不到正确的序列了，但最后算出来的个数是没错的，为什么呢？
想想，当temp>top时，总个数直接加1，这肯定没错;但当temp<top时呢？这时temp肯定只是替换了栈里面的某一个元素，所以大小不变，就是说一个小于栈顶的元素加入时，总个数不变。这两种情况的分析可以看出，如果只求个数的话，这个算法比较高效。但如果要求打印出序列时，就只能用DP了。

code

class Solution {
public:
    /**
     * @param nums: The integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    int longestIncreasingSubsequence(vector<int> nums) {
        // write your code here
        int size = nums.size(), i = 0;
        vector<int> stack;

        if(size <= 0) {
            return 0;
        }

        stack.push_back(nums[0]);
        for(i=1; i<size; i++) {
            if(stack[stack.size()-1] < nums[i]) {
                stack.push_back(nums[i]);
            }
            else {
                int low = 0, high = stack.size()-1, mid = 0;
                while(low <= high) {
                    mid = low + (high - low) / 2;
                    if(nums[i] > stack[mid]) {
                        low = mid + 1;
                    }
                    else {
                        high = mid - 1;
                    }
                }
                stack[low] = nums[i];
            }
        }
        return stack.size();
    }
};