最大不下降子序列c++
时间: 2023-05-25 08:04:31 浏览: 62
最大不下降子序列是指在一个序列中选取若干个元素,这些元素保持原来在序列中的相对顺序,且元素值不递减。例如,序列{3, 1, 4, 1, 5, 9, 2, 6}的最大不下降子序列可以是{3, 4, 5, 9}或者{1, 4, 5, 9}等,其中第一个子序列的长度为4,为所有不下降子序列中最长的。
求解最大不下降子序列问题的算法有多种,其中比较经典的算法是动态规划。具体做法是利用一个辅助数组dp,dp[i]表示以第i个元素结尾的最大不下降子序列的长度。显然,当i=0时,dp[i]=1,因为以第一个元素结尾的最大不下降子序列只有它一个元素。当i>0时,dp[i]的取值需要根据前面元素的状态来决定,即:
1. 若第i个元素比前面的所有元素都小,则dp[i]=1;
2. 否则,以第i个元素结尾的最大不下降子序列的末尾必然是第j个元素(j<i),且j可以是任何满足条件的位置,因此dp[i]的取值为max(dp[j])+1,其中max(dp[j])表示所有满足j<i且a[j]<=a[i]的最大dp值。
最终,最大不下降子序列的长度就是dp数组中的最大值。
以下是python代码实现:
def max_non_dec_seq(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)
print(max_non_dec_seq([3, 1, 4, 1, 5, 9, 2, 6])) # 4