7-6 上升子序列SDUT

上升子序列是指在一个序列中，如果一些数字呈上升趋势排列，那么这些数字就可以组成一个上升子序列。比如序列 {1, 3, 5, 2, 4, 6} 中，{1, 3, 5} 和 {2, 4, 6} 就是两个上升子序列。

SDUT（Shandong University of Technology，山东理工大学）的上升子序列问题是这样的：给定一个长度为 n 的序列，找出其中的一个最长的上升子序列。例如，对于序列 {1, 4, 3, 5, 6, 2}，其最长的上升子序列为 {1, 4, 5, 6}，长度为 4。

求解这个问题可以使用动态规划算法。我们可以定义一个数组 dp，其中 dp[i] 表示以第 i 个数字为结尾的最长上升子序列的长度。初始时，dp[i] 的值都为 1，因为每个数字本身就可以组成一个长度为 1 的上升子序列。然后，我们从第 2 个数字开始依次计算 dp[i] 的值，计算方法如下：

- 对于第 i 个数字，我们枚举它前面的所有数字 j，如果 j 小于 i，那么 dp[i] 的值可以更新为 dp[j]+1（因为以 j 为结尾的最长上升子序列再加上数字 i 就可以得到以 i 为结尾的最长上升子序列）。
- 在枚举 j 的过程中，我们还需要维护一个变量 max_len，它表示所有 dp[j]+1 的最大值。这是因为以 i 为结尾的最长上升子序列并不一定是以 j 为结尾的最长上升子序列再加上一个数字 i 得到的，有可能是以 j 为结尾的最长上升子序列和以 i 为结尾的最长上升子序列中的某个更长的子序列拼接得到的。
- 最终，我们遍历整个 dp 数组，找出其中的最大值即可。

下面是 Python 代码实现：

def longest_increasing_subsequence(nums):
    n = len(nums)
    dp = [1] * n
    max_len = 1
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j]+1)
        max_len = max(max_len, dp[i])
    return max_len

时间复杂度为 O(n^2)。