最长上升子序列(一)

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

热度指数：62051 时间限制：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

算法知识视频讲解

一个优雅的程序猿

#define max(a,b) (a>b?a:b)
int LIS(int* arr, int arrLen ) {
    int dp[1000]={1}, res=1, i, j;
    if(arrLen==0)
        return 0;
    for(i=0; i<sizeof(dp)/sizeof(int); i++)
        dp[i] = 1;
    for(i=1; i<arrLen; i++) {
        for(j=0; j<i; j++) {
            if(arr[i]>arr[j]) {
                dp[i] = max(dp[i], dp[j]+1);
                res = max(res, dp[i]);
            }
        }
    }
    return res;    
}

编辑于 2024-03-24 19:06:41 回复(0)