最长上升子序列 算法

最长上升子序列(Longest Increasing Subsequence, LIS)是指在一个序列中找到一个子序列，使得这个子序列是单调递增的，并且长度最长。

举个例子，对于序列 [5, 3, 4, 8, 6, 7]，最长上升子序列为 [3, 4, 6, 7]，长度为 4。

最长上升子序列可以使用贪心算法或动态规划算法来解决。

贪心算法

假设我们已经找到了从前往后的一个子序列，并且这个子序列是单调递增的。我们可以使用贪心策略，对于新的元素，如果它大于当前子序列的最后一个元素，就将它加入子序列的末尾；如果它小于当前子序列的最后一个元素，就用它替换当前子序列的最后一个元素。这样我们就可以保证在每一步都选择了最优的方案。

代码实现如下：

def LIS(arr):
    n =len(arr)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)
1
2
3
4
5
6
7
8
9

动态规划算法

动态规划算法也可以用来解决最长上升子序列问题。我们可以使用一个数组 dp[i] 表示以第 i 个元素结尾的最长上升子序列的长度。