最长上升子序列(动态规划)

[any86]

思路

1. 已知一维数组[1,2,7,5,9], 我们叫他nums
2. 新建一个数组dp, 存储nums中索引为i的数字作上升子序列最后一位时该子序列的最大长度
3. 通过双层循环, 我们比对前一个数和当前数字(索引为i)的大小关系,
   如果当前数字大于前一个那么dp[i]等于dp[j]+1, 但是如果dp[j]+1还没有dp[i]大, 说明dp[j]不在连续的递增子序列中, 所以dp[i]的不做修改(依旧等于dp[i]);

function lengthOfLIS (nums) {
    const { length } = nums;
    const dp = new Array(length);

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

[any86]

参考 https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-t/