Dynamic programming - maximum sum increasing sub sequence

Question

Given an array of n positive integers. this is a program to find the sum of maximum sum subsequence of the given array such that the integers in the subsequence are in increasing order. I am trying to implement the code based on this YouTube video I do not know what I am doing wrong.

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

four_lines · Accepted Answer · 2017-06-10 17:18:36Z

1

In Python, when you do list1 = list2, you don't get two lists. list1 becomes a reference of list2. Essentially the two variables refer to the same list.

So change it to list1 = list2[:] to copy the values from one list to another. The following should work:

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

answered Jun 10, 2017 at 17:18

four_lines

5033 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

ujjal das · Accepted Answer · 2018-12-20 17:42:39Z

0

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)

answered Dec 20, 2018 at 17:42

ujjal das

94711 silver badges16 bronze badges

Collectives™ on Stack Overflow

Dynamic programming - maximum sum increasing sub sequence

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related