动态规划-python

解题思路:其实就是求最大不下降子序列和最大不上升子序列，我的r【i】数组表示以num【i】结尾的最长不降序子序列的长度，d【i】表示以num【i】开头的最大不上升子序列，就是先上后下类似于一个抛物线，找到一个最合适的点就是答案，然后要注意不能连续浏览相同海拔的两个景点，我们就额外定义一个变量，记录上一个浏览景点的海拔就行了。

注意事项:

参考代码:

n=int(input())
num=list(map(int,input().split()))
r=[1]*n
d=[1]*n
max_dp=0
for i in range(n):
    last=num[i]
    for j in range(i-1,-1,-1):
        if num[j]<=num[i] and r[j]+1>max_dp and num[j]!=last:
            max_dp=r[j]+1
            last=num[j]
    if max_dp==0:
        continue
    r[i]=max_dp
    max_dp=0
max_dp=0
for i in range(n-1,-1,-1):
    last=num[i]
    for j in range(i+1,n):
        if num[j]<=num[i] and d[j]+1>max_dp and num[j]!=last:
            max_dp=d[j]+1
            last=num[j]
    if max_dp==0:
        continue
    d[i]=max_dp
    max_dp=0
ans=0
for i in  range(n):
    ans=max(ans,r[i]+d[i])
print(ans-1) #答案要减1，因为一上一下，顶峰的位置多加了1