登山-线性动态规划的一种特殊情况

解题思路:

注意事项:

参考代码:

"""

线性动态规划 时间复杂度 N**2

除了要考虑上升的情况还要考虑先上升和下降

前面一种实现起来很简单

对于后面一种 要考虑更多的东西-比如数据重复和数据来源

"""

num=eval(input())

data=list(map(int,input().split()))

# 下面的Map设置比较有讲究-总之最少的情况就是它本身1个数据怎么都不会有问题

Map=list([[data[i-1]],[data[i-1]]] for i in range(num+1))

for i in range(2,num+1):

    for j in range(1,i):

        # 情况1持续上升

        if data[i-1]>Map[j][0][-1]:

            list1=Map[j][0]+[data[i-1]] # []

            if len(list1)>len(Map[i][0]):

                Map[i][0]=list1

        # 情况2持续下降 可能重复

        # 为啥要用两个if呢 第一个if更新数据 因为在先上升后下降,前面上升的数据

        # 需要一直更新 才能给下降的数据更多的考虑

        # 下降的数据也需要遇到下降的数据

        if data[i-1]<Map[j][0][-1] and data[i-1] not in Map[j][0]:

            list1=Map[j][0]+[data[i-1]]

            if len(list1)>len(Map[i][1]):

                Map[i][1]=list1

        if data[i-1]<Map[j][1][-1] and data[i-1] not in Map[j][1]:

            list1=Map[j][1]+[data[i-1]]

            if len(list1)>len(Map[i][1]):

# 处理Map

sum1=0

for i in Map:

    if len(i[0])>sum1:

        sum1=len(i[0])

    if len(i[1])>sum1:

        sum1=len(i[1])

print(sum1)