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

如何体现上升的逻辑？

定义DP数组存放的是以当前位置i结尾的子序列中的最长上升子序列长度，此时可以在0到i的所有子数组中寻找上升子序列，因为是0到i的子数组，所以保证了j<i，所以当arr[j]<arr[i]时，说明i是上升子序列的一部分，则此时以arr[i]结尾的上升子序列长度为dp[i]=1+dp[j]。

如何思考状态转移方程？

在0到i的子数组中，遍历每个子数组时都更新dp[i]为当前子数组中以arr[i]结尾的最大子序列长度，dp[i] = max(dp[i], dp[j]+1)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 给定数组的最长严格上升子序列的长度。
 * @param arr int整型一维数组 给定的数组
 * @return int整型
 */
function LIS( arr ) {
    // write code here
    const dp = new Array(arr.length).fill(1);  // 存放以每个位置结尾的子序列中的最长上升子序列长度，因为数组中至少有一个元素，而且要更新最大值，因此初始值设置为最小值1

    for (let i = 0; i < arr.length; ++i) {
        for (let j = 0; j < i; ++j) {  // 求从0到i的子数组中的最长上升子序列长度
            if (arr[j] <= arr[i]) {  // 体现上升逻辑，arr[i]是子序列的末尾，且arr[j] < arr[i]说明是上升的，此时更新dp[i]即以arr[i]为上升子序列末尾的最大长度
                dp[i] = Math.max(dp[j]+1, dp[i]);
            }
        }
    }

    return arr.length === 0? 0 : Math.max(...dp);  // 找到所有位置为上升子序列末尾时的最长子序列长度，注意可能有空数组的情况
}
console.log(LIS([6,3,1,5,2,3,7]))
module.exports = {
    LIS : LIS
};