Skip to content

51Nod 2080 最长上升子序列#

目录#

1. 题目描述#

1.1. Limit#

Time Limit: 1000 ms

Memory Limit: 131072 kB

1.2. Problem Description#

一个数列的最长上升子列，是指其所有递增的子列中最长的一个子列

给定一个长度为 的数列 ，求这个数列的最长上升子列的长度

例如对数列 1 7 2 8 3 4，这个数列的最长递增子数列是 1 2 3 4，长度为 4；次长的长度为 3， 包括 1 7 8、1 2 3 等。

1.3. Input#

第一行一个正整数 ，表示数列元素个数，

第二行 个正整数，从左到右给出数列的每一项

1.4. Output#

一行一个正整数，表示最长上升子数列的长度

1.5. Sample Input#

8
5 1 6 8 2 4 5 10

1.6. Sample Output#

5

1.7. Source#

51Nod 2080 最长上升子序列

2. 解读#

通过动态规划求解最长上升子序列。

定义状态 ，表示以第 个数为结尾的最长递增子序列的长度，那么：

满足以下条件

和 表示序列中第 和第 个数的数值 1 。

最后答案为

3. 代码#

#include <iostream>
using namespace std;

#define MAXN 1001

int n, list[MAXN];

// 求最长上升子序列长度
int LIS()
{
    int ans = 1;
    int dp[MAXN];
    dp[1] = 1;
    // 对所有数进行循环
    for (int i = 0; i <= n; i++) {
        int max = 0;
        // 对所有小于i的数进行循环
        for (int j = 1; j < i; j++) {
            // 若找到符合条件的最大值
            if (dp[j] > max && list[j] < list[i]) {
                // 记录最大值
                max = dp[j];
            }
        }
        // 将当前遍历的数位计算在内，当前的最长上升子序列长度为max + 1
        dp[i] = max + 1;
        if (dp[i] > ans) {
            ans = dp[i];
        }
    }
    return ans;
}

int main()
{
    while (cin >> n) {
        for (int i = 1; i <= n; i++) {
            cin >> list[i];
        }
        cout << LIS() << endl;
    }
    return 0;
}

4. 参考文献#

[1] 罗勇军, 郭卫斌. 算法竞赛入门到进阶 [M]. 北京: 清华大学出版社, 2019.

联系邮箱：curren_wong@163.com

Github：https://github.com/CurrenWong

欢迎转载/Star/Fork，有问题欢迎通过邮箱交流。

Back to top