动态规划-最大和递增子序列

Question

给定n个正整数的数组。这是一个寻找给定数组的最大和子序列的和的程序，使得子序列中的整数按升序排列。我试图实现基于这个YouTube视频的代码，我不知道我做错了什么。

 class MaxIncreasingSumSubSequence(object):
        def incsum(self,nums):
            maxvalue = 0
            sumlist = nums
            for i in range(1,len(nums)):
                for j in range(i):
                    if nums[j] < nums[i] and nums[i] + sumlist[j] > sumlist[i]:
                        sumlist[i] = nums[i] + sumlist[j]
            maxvalue = max(sumlist)
            print(maxvalue)

MaxIncreasingSumSubSequence().incsum([1, 101, 2, 3, 100, 4, 5])

Answer 1

def fun(a):
    n=len(a)
    list_sum=[a[0]]
    max_val=a[0]
    for i in range(1,n):
        temp=a[i]
        j=i-1
        while j>-1:
            if a[j]<a[i]:
                if temp<a[i]+list_sum[j]:
                    temp=a[i]+list_sum[j]
                if list_sum[j]==max_val:
                    break

            j-=1
        list_sum.append(temp)
        if temp>max_val:
            max_val=temp

    return max_val
 fun(array)

Answer 2

在Python中，当您执行list1=list2时，您不会得到两个列表。list1成为list2的引用。本质上，这两个变量引用同一个列表。

因此，将其更改为list1=list2[：]以将值从一个列表复制到另一个列表。以下操作应有效：

def incsum(nums):
    sumlist = nums[:]
    for i in range(1,len(nums)):
        for j in range(0,i):
            if nums[j] < nums[i] and nums[i] + sumlist[j] > sumlist[i]:
                sumlist[i] = nums[i] + sumlist[j]
    print(max(sumlist))

incsum([1, 101, 2, 3, 100, 4, 5])