题解 | #最长上升子序列(一)#

1.错误思路

看到示例

7
6 3 1 5 2 3 7

首先想到了用单调栈，因为单调栈可以得到递增子序列，那么以数组每个元素$ii$为结尾，向前查找最长的单调递减子序列

function main(arr, n) {
    let max = 1
    let stack = null
    for(let i = 1 ; i < n ; i++) {
        stack = [arr[i]] 
        for(let k = i - 1 ; k >= 0 ; k--) {
            let peek = stack[stack.length - 1]
            if(arr[k] < peek) stack.push(arr[k])
        }
        max = Math.max(max, stack.length)
    }
    return max
}

该方法将得到错误的结果，例如

6
1 2 3 4 3 5

该示例结果应该为5，但实际输出为4，因为从5向前递减，元素3已经决定了再之前的元素不能大等于3，而实际5之前的元素应该是4。考虑到这个问题，那或许就会联想到动态规划了，因为动态规划可以通过状态转移来避免上述单调栈所出现的问题，即我可以同时考虑元素4到元素5的状态转移，以及元素3到元素5的状态转移，两者取大值。

2.动态规划

动态规划的思路其实就是修改单调栈的缺陷，以元素$arr[i]arr[i]$为子序列结尾元素，查找最长递增子序列。状态转移方程则是当$arr[i]>arr[k]arr[i]\; >\; arr[k]$的时候，$dp[i]=dp[k]+1dp[i]\; =\; dp[k]\; +\; 1$，当然由于$kk$有多个值，我们要找最大值，则状态转移方程改为$dp[i]=max(dp[i],dp[k]+1)dp[i]\; =\; max(dp[i],\; dp[k]\; +\; 1)$

3.JavaScript实现

const n = ~~readline()
const arr = readline().split(' ').map(x => parseInt(x))

function main(arr, n) {
    let max = 1
    const dp = new Array(n).fill(1)
    for (let i = 1; i < n; i++) {
        for (let k = 0; k < i; k++) {
            if (arr[i] > arr[k]) {
                dp[i] = Math.max(dp[i], dp[k] + 1)
            }
        }
        max = Math.max(max, dp[i])
    }
    return max
}

console.log(main(arr, n))