题目描述

Longest Increasing Subsequence

给定一个无序的数字数组，找到它最长的上升子序列

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. 

另：

• 最长子序列的组合可能不止一个，只需要返回最长的长度
• 时间应该为复杂度为 O(n²), 能不能尝试优化到 O(nlogn)

From leetcode No.300 Medium (opens new window)

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    
};

解法

动态规划

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
    let max = 0
    const f = new Array(nums.length).fill(1)
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]){
                f[i] = Math.max(f[j] + 1, f[i])
            }
        }
        max = Math.max(max, f[i])
    }
    return max
};

贪心算法

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
    const len = nums.length
    if(len === 0)
        return 0
    const dp = [nums[0]]
    for(let i=1; i<len; i++){
        const curr = nums[i]
        if(curr > dp[dp.length - 1]){
            dp.push(curr)
        }else{
            for(let j=0; j<dp.length; j++){
                if(curr <= dp[j]){
                    dp[j] = curr
                    break;
                }
            }
        }
    }
    return dp.length
};

总结

• dp的思想很重要, 以 nums 上索引为n的 lengthOfLIS 为 f(n), 就满足:
  • 数组为空时， f(n) = 0
  • 不为空时，f(n) 最小值为 1(最坏情况，整个数组单调递减)
  • n > 0 时，满足

    if(nums[n] > nums[n-1]){
        f(n) = f(n-1) + 1
    }
    

• 求最长lengthOfLIS，即求 f(n)的最大值，即为：Math.max(...[f(0), f(1), ..., f(n)])

注意

这里要注意的是 f(n) 与 f(n-1)的关系，不一定存在 f(n) >= f(n-1) 的关系

除此之外，还有一种思路，即贪心算法

• 这里充分利用了题目条件，只要求返回最长上升序列的长度，而非最长子序列本身
• 创建一个数组 dp存当前上升子序列，依次迭代原数组 nums中的元素放入其中
  • 如果当前数字比 dp最后一个元素大，就追加到最后
  • 如果比 dp最后一个元素小，就让它替换 dp中一个合适元素。 这个合适元素可能是最后一个元素，也可能是它之前的元素，替换后需保持 dp继续单调递增。 这里即是“贪心”的解释：保证最后一个元素尽量的小，这样上升序列才会尽可能长
  • eg: nums为 [3, 2, 4, 1], 按照上述规则，dp依次是
    • [3]
    • [2]
    • [2, 4]
    • [1, 4] 虽然 dp不是真正符合题目要求的上升子序列， 但它的长度是与目标最长上升子序列 [3, 4]或 [2,4]是一样的， 且它们的最后一位肯定是相同的。
  • dp 的实际含义是，dp[n] 表示长度为 n + 1的最长子序列的末尾元素

另，查找合适元素的方法改成二分查找，可进一步让复杂度降低到O(nlogn)

贪心 + 二分查找

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
    const len = nums.length
    if (len === 0)
        return 0
    const dp = [nums[0]]
    for (let i = 1; i < len; i++) {
        const curr = nums[i]
        if (curr > dp[dp.length - 1]) {
            dp.push(curr)
        } else {
            let left = 0
            let right = dp.length - 1
            while (left < right) {
                const mid = Math.floor((left + right) / 2)
                const val = dp[mid]
                if (curr <= val) {
                    right = mid
                } else {
                    left = mid + 1
                }
            }
            dp[right] = curr
        }
    }
    return dp.length
};

参考

• longest-increasing-subsequence (opens new window)