300. Longest Increasing Subsequence

[Tcdian]

300. 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?

[Tcdian]

Solution 1 ( DP )

• JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number}
 */

// 解法一: dp
// dp[i] 表示以 nums[i] 为结尾的最长递增子序列
// 时间复杂度 O(n^2)

var lengthOfLIS = function(nums) {
    const dp = new Array(nums.length).fill(1);
    let result = 0;

    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
        result = Math.max(result, dp[i]);
    }

    return result;
};

[Tcdian]

Solution 2 ( Binary Search )

• JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number}
 */

// 解法二: 
// 维护一个 increasingSequence 数组，记录当前长度结尾的递增子序列的最小结尾。
// 利用二分查找查找降低 increasingSequence 中元素查找的时间复杂度
// 时间复杂度 O(nlogn)

var lengthOfLIS = function(nums) {
    const increasingSequence = [];
    
    for (let i = 0; i < nums.length; i++) {
        if (
            increasingSequence.length === 0
                || increasingSequence[increasingSequence.length - 1] < nums[i]
        ) {
            increasingSequence.push(nums[i]);
        } else {
            let l = 0;
            let r = increasingSequence.length - 1;
            while(l < r) {
                const mid = Math.floor((l + r) / 2);
                if (increasingSequence[mid] < nums[i]) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
            increasingSequence[l] = nums[i];
        }
    }

    return increasingSequence.length;
};