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

Question

给定一个包含 n 个正整数的数组。这是一个程序，用于查找给定数组的最大和子序列的总和，使得子序列中的整数按递增顺序排列。我正在尝试基于此 YouTube video 实现代码我不知道我做错了什么。

 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

在 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])