895 最长上升子序列

旧城等待， 2022-09-11 11:12 118阅读 0赞

**1. 问题描述：**

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

**输入格式**

第一行包含整数 N。第二行包含 N 个整数，表示完整序列。

**输出格式**

输出一个整数，表示最大长度。

**数据范围**

1 ≤ N ≤ 1000，  
−10 ^ 9 ≤ 数列中的数 ≤ 10 ^ 9

**输入样例：**

7  
3 1 2 1 8 5 6

**输出样例：**

4  
来源：[https://www.acwing.com/problem/content/description/897/][https_www.acwing.com_problem_content_description_897]

**2. 思路分析：**

**最长上升子序列问题**属于动态规划中的一类经典问题，对于动态规划的问题我们主要是分为两个步骤进行处理：① 状态表示；② 状态计算；状态表示主要是结合题目求解的问题进行定义的，由题可知我们需要求解所有以a\[i\]结尾的严格单调上升的子序列长度的最大值，并且由于是一维的序列所以我们可以定义一个一维数组dp，其中dp\[i\]表示以当前的a\[i\]结尾的严格单调上升的子序列长度的最大值，状态计算对应集合的划分，一般是找最后一个不同点，可以发现最后一步都是a\[i\]，所以不好直接划分集合，我们可以按照倒数第二步的数字进行划分，也即最后一个不同点，这样可以划分为i类，对应的集合为a\[0\]，a\[1\]，...a\[i - 1\]和不存在的情况，那么可以得到对应的状态转移方程为：dp\[i\] = max(dp\[i\]，dp\[j\] + 1)，j = 0，1，2...，i - 1，时间复杂度为O(n ^ 2)，除了这种朴素的做法之外，其实还有一种比较优秀的做法是：贪心 + 二分。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_14_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

if __name__ == "__main__":
        n = int(input())
        nums = list(map(int, input().split()))
        n = len(nums)
        dp = [0] * n
        res = 0
        for i in range(n):
            # 当为空集的时候为1, 也即只有当前的数字才满足上升子序列的要求
            dp[i] = 1
            for j in range(i):
                # 判断是否可以将当前的数字添加到之前序列的后面
                if nums[i] > nums[j]: 
                    dp[i] = max(dp[i], dp[j] + 1)
                    # 在求解的时候更新一下答案
                res = max(res, dp[i])
        print(res)

[https_www.acwing.com_problem_content_description_897]: https://www.acwing.com/problem/content/description/897/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/177762b2275d45fb8888fcf309744c68.png