動的プログラミング - 最大合計増加サブシーケンス

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を実行すると2つのリストが表示されません。 list1はlist2の参照になります。基本的に2つの変数は同じリストを参照します。

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