动态规划——求最长不下降子序列（python详解）

解题思路:吐槽官方，写了一大堆，然后说我的题目太短，结果写的全没了！！！

 dp【i】的含义为，以b【i】结尾的最长不下降子序列是多少

然后我们要确定上一状态，首先如果我们以b【i】结尾，那么我们得上一个数一定要小于等于b【i】，光小于不行，我要找到最优的倒数第二个数，我想要它的dp尽可能大，这样我得到的才是一个最长的不下降子序列，dp【i】初始化都为1，这也很好理解，如果最后一个数的前面没有小于等于他的数，那么我这个序列就我一个，就是1，最后我们遍历所有的dp得出一个最大的数就是答案

还有个问题我们要输出子序列，我们可以通过ans（最长不下降子序列的长度），确定我们其中的一个子序列的结尾的数，用dp.index(ans)就能找到它的下标，就能在b中找到它的值，然后我们通过dp【i】=dp【j】+1，b【j】<=b【i】可以确定j,我们就可以由最后一个数逐渐往前推，推出所有的数

大概是这个意思，之前写的很多，心态崩了。
建议自己敲一遍代码，跟着思路来一遍，这类题型还是较基础的，这种方法也是复杂度最高的O(n**2)，也有别的方法实现O(nlog（n）),但我不会，可以去别的地方查一下
注意事项:

参考代码:

n=int(input())
b=list(map(int,input().split()))
max_dp=0
dp=[1]*n    #初始化
for i in range(1,n):
  for j in range(i-1,-1,-1):
      if b[j]<=b[i] and dp[j]+1>max_dp:   #找最优的倒数第二个数，首先要小于扥关于倒数第一个数，然后希望它的dp尽可能大
          max_dp=dp[j]+1
  if max_dp==0:        #前面没有比自己大的数就跳到下一次循环
      continue
  dp[i]=max_dp
  max_dp=0
ans=0
for i in range(n):
  ans=max(ans,dp[i])          #遍历所有的dp找到我们要的最长不下降子序列，ans是我们要的答案
print('max=%d'%ans)
p=dp.index(ans)       #因为最长不下降子序列不唯一，题目中也说明只要写出一种就行，因此这里可以使用index（默认找到第一个ans），p为第一最长不下降子序列的最后一个数的下标
last=b[p]
wd=[]             #存放最后的答案
wd.append(b[p])
la=p               #后一个数的下标
for i in range(p-1,-1,-1):
  if b[i]<=last and dp[i]==dp[la]-1:   #这里要定义一个变量la，用index会出错，因为你的序列中可能有相同的数
      wd.append(b[i])
      last=b[i]
      la=i
for i in range(len(wd)-1,-1,-1):   #倒叙输出就是答案
  print(wd[i],end=' ')