最长递增子序列算法伪代码

以下是最长递增子序列（Longest Increasing Subsequence, LIS）的动态规划算法伪代码：

输入：序列 a，长度为 n

LIS = [1]*n // 初始化 LIS 数组，LIS[i] 表示以 a[i] 结尾的 LIS 长度为 1
for i = 1 to n do
for j = 1 to i-1 do
if a[j] < a[i] then
LIS[i] = max(LIS[i], LIS[j]+1)
输出：max(LIS) // LIS 数组的最大值即为最长递增子序列的长度

其中 max 函数表示取最大值。时间复杂度为 O(n^2)。

相关问题

设计算法，用于找出由n个数构成的序列的最长单调递增子 给出伪代码

要设计一个算法来找出由 n 个数字组成的序列的最长单调递增子序列 (LIS)，你可以使用动态规划。这里提供一个基于这个思想的伪代码：

function longest_increasing_subsequence(sequence):
    # 初始化长度数组，所有元素为1，因为每个元素本身都是一个单元素的递增子序列
    dp [0 ... n] = {1} for i in range(n)

    # 遍历整个序列
    for i from 1 to n:
        # 对于当前元素 sequence[i]，找到它的前一个元素 j，使得 sequence[j] < sequence[i]
        for j from 0 to i - 1:
            if sequence[j] < sequence[i]:
                # 更新dp[i]，如果新组合的长度比已知的更大，则更新为dp[j] + 1
                dp[i] = max(dp[i], dp[j] + 1)

    # 最终dp[n]就是所求的最长递增子序列的长度
    return dp[n]

# 示例：
length = longest_increasing_subsequence([10, 9, 2, 5, 3, 7, 101, 18])

给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱） 例如：给定一个长度为8的数组A{1，3，5，2，4，6，7，8}，则其最长的单调递增子序列为{1，2，4，6，7，8}，长度为6。 输入：数组，数组长度 输出：输出该数组最长递增子序列的长度

这个问题可以使用动态规划（Dynamic Programming）中的滑动窗口（Sliding Window）算法来解决。首先，创建两个变量，`end`记录当前找到的最长递增子序列的结尾位置，`length`存储最长递增子序列的长度。

初始化 `end = 0` 和 `length = 1`（因为第一个元素本身就是单个递增子序列）。接下来，遍历数组从索引1开始：

1. 检查 `arr[end] < arr[i]`，如果满足条件（即当前元素大于前一个子序列的最后一个元素），说明找到了一个新的递增子序列的起点，将 `end` 更新为 `i`，并将 `length` 加一。
2. 如果 `arr[end] >= arr[i]`，说明当前位置无法延长递增子序列，需要回溯到下一个可能的位置，这时更新 `end` 为 `i - 1`，并检查 `arr[end + 1]` 是否能继续增加，若能，则更新 `end`。

遍历结束后，`length` 就是所求的最长递增子序列的长度。

下面是一个伪代码示例：

function findLongestMonotonicSubsequence(arr):
    length = 1
    end = 0

    for i in range(1, len(arr)):
        if arr[end] < arr[i]:
            length += 1
            end = i
        else:
            while (end > 0 and arr[end] >= arr[i]):
                end -= 1
            end += 1

    return length