如題

因為要求的是連續子序列和的最大值，所以分類應為c[i]要不要i之前的序列

對于第i個元素，

1）要i之前的序列，則table[i1]+c[i]

2）不要i之前的序列，則c[i]

取兩者里邊的最大值給了table[i]

?

numpy.argmax(list)? ?:返回列表中最大元素的索引

詳解argmax

            
              def bottom_up_seque(c):
    lent=len(c)
    table=[None]*(lent+1)
    table[0]=0
    table[1]=c[0]
    for i in range(2,lent+1):
        table[i]=max(table[i-1]+c[i-1],c[i-1])
    return table

def back_seque(table,c):
    select=[]
    import numpy
    lent=len(table)
    max_sum=max(table)  #max_sum為table中的最大值
    max_i=numpy.argmax(table)  #max_i為table中最大元素的索引
    i=max_i
    while max_sum>0:
        max_sum-=c[i-1]
        select.append(c[i-1])
        i-=1
    return select


if __name__=="__main__":
    c=[-2,11,-4,13,-5,2]
    temp=bottom_up_seque(c)
    select=back_seque(temp,c)
    print("動態規劃表：")
    print(temp)
    print(select[::-1])
            
          

?