最长不上升子序列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

最长上升子序列是指在一个给定序列中，找到一个最长的子序列，使得子序列中的元素是严格递增的。下面是一个用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。

二分法最长上升子序列

二分法最长上升子序列问题是一个经典的动态规划问题。它的解决方法并不是使用二分法，而是利用动态规划的思想。

首先，我们定义一个数组 dp，其中 dp[i] 表示以第i个元素结尾的最长上升子序列的长度。初始化时，将 dp 数组的所有元素都设为1。

然后，我们遍历数组，并对于每个元素 nums[i]，再遍历其前面的所有元素 nums[j]（其中 0 ≤ j < i）。如果 nums[i] 大于 nums[j]，则更新 dp[i] 的值为 dp[j] + 1，表示以第i个元素结尾的最长上升子序列的长度比以第j个元素结尾的最长上升子序列的长度多1。

最后，遍历 dp 数组，找到其中的最大值，即为所求的最长上升子序列的长度。

以下是一个示例代码实现：

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

希望对你有所帮助！如果还有其他问题，请继续提问。