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?
我們使用一個(gè)數(shù)組tail，這個(gè)數(shù)組的第i個(gè)元素保存著長(zhǎng)i+1的增序列中結(jié)尾最小的序列的結(jié)尾
比如：[10, 9, 2, 5, 3, 7, 101, 18]。這個(gè)數(shù)組就是：[2,3,7,18]。
對(duì)應(yīng)的序列是：[2],[2,3],[2,3,7],[2,3,7,18]。
可以發(fā)現(xiàn)這個(gè)數(shù)組一定是不減的。
那么我們從頭開始遍歷整個(gè)數(shù)組，對(duì)于每一個(gè)元素，我們?cè)趖ail里二分找一下：
如果它大于tail里的每一個(gè)元素，那就意味著有一個(gè)新的長(zhǎng)度的增序列出現(xiàn)了，我們把這個(gè)元素放到tail的末尾；
如果它不大于所有元素，找到第一個(gè)大于等于它的，換掉這個(gè)元素。
最后最長(zhǎng)子數(shù)組的長(zhǎng)度就是tail數(shù)組的長(zhǎng)度。

var lengthOfLIS = function(nums) {
    var tails = [];
    var size = 0;
    var num = nums.length;
    for (var i = 0;i < num;i++) {
        var left = 0, right = size;
        while (left != right) {
            var m = parseInt((left + right) / 2);
            if (tails[m] < nums[i])
                left = m + 1;
            else
                right = m;
        }
        tails[left] = nums[i];
        if (left == size) ++size;
    }
    return size;
};