最长上升子序列python

最长上升子序列是指在一个给定序列中，找到一个最长的子序列，使得子序列中的元素是严格递增的。下面是一个用Python实现最长上升子序列的例子：

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

nums = [10, 9, 2, 5, 3, 7, 101, 18]
result = longest_increasing_subsequence(nums)
print(result)

这段代码中，我们使用动态规划的思想，定义一个dp数组，dp[i]表示以第i个元素结尾的最长上升子序列的长度。初始时，每个元素自成一个长度为1的上升子序列。然后，我们遍历数组，对于每个元素nums[i]，通过比较nums[i]与之前的元素nums[j]的大小关系，更新dp数组中的值。最后，返回dp数组中的最大值即可。在给定的例子中，最长上升子序列是[2, 3, 7, 101]，其长度为4。

相关问题

最长不上升子序列python

以下是一个使用动态规划的Python程序，用于查找最长不上升子序列：

def longest_non_increasing_subsequence(arr):
n = len(arr)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if arr[j] >= arr[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)

arr = [5, 2, 8, 6, 3, 6, 9, 7]
print(longest_non_increasing_subsequence(arr)) # 输出为 4

该程序的时间复杂度为O(n^2)，其中n是序列的长度。

# 最长上升子序列问题：给定一个无序的整数数组，找到其中最长上升子序列的长度。 python

可以使用动态规划来解决这个问题。具体来说，我们定义dp[i]表示以第i个数字为结尾的最长上升子序列的长度。因此，我们需要遍历i之前的所有数字，找到比第i个数字小的数字j，然后更新dp[i]=max(dp[i], dp[j]+1)。最终的答案就是dp数组中的最大值。

下面是Python代码实现：

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

例如，对于数组[10,9,2,5,3,7,101,18]，最长上升子序列是[2,5,7,101]，其长度为4。