最长上升子序列(一)

[编程题]最长上升子序列(一)

热度指数：62849 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。

所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。

我们定义一个序列是 严格上升 的，当且仅当该序列不存在两个下标 $i$ 和 $j$ 满足 $i<j$ 且 $arr_i \geq arr_j$ 。

数据范围： $0\leq n \leq 1000$

要求：时间复杂度 $O(nlogn)$ ，空间复杂度 $O(n)$

示例1

输入

[6,3,1,5,2,3,7]

输出

说明

该数组最长上升子序列为 [1,2,3,7] ，长度为4

算法知识视频讲解

Javascript

达拉崩吧、

js实现代码如下：

function LIS(arr) {
    const n = arr.length;
    if (n === 0) return 0;
    const dp = new Array(n).fill(1);
    let max = 1;
    for (let i = 1; i < n; i++) {
        let j = i - 1;
        while (j >= 0 && j >= dp[i] - 1) {
            if (arr[j] < arr[i]) {
                dp[i] = Math.max(dp[j] + 1, dp[i]);
                console.log(i, dp[i]);
            }
            j--;
        }
        if (dp[i] > max) {
            max = dp[i];
        }
    }
    return max;
}

发表于 2023-08-08 10:53:49 回复(0)