How can I store the elements(indexes) that produced the maximum sum where non-adjacent numbers were picked in a given array (Dynamic programming)

user_15242858 0
Viewed 82

I'm new to dynamic programming in python and this is the code I have done so far to get the numbers that give the max sum from the array. However, my code doesn't work for input array A Here are cases:

Test cases:
A = [7,2,-3,5,-4,8,6,3,1]
B = [7,2,5,8,6]
C = [-2,3,1,10,3,-7]

Output:
A = [7,5,8,3]
B = [7,5,6]
C = [3,10]

My output works for B and C but not for array A. The output I get is this: [7,6,1]

And Here is my code:

def max_sum(nums):
    #Get the size of the array
    size = len(nums)
    list = []
    cache = [[0 for i in range(3)] for j in range(size)]

    if(size == 0):
        return 0

    if (size == 1):
        return nums[0]

    for i in range(0, size):
        if(nums[i] < 0):
            validate = i

    if(size  == validate + 1):
        return []
    #Create array 'cache' to store non-consecutive maximum values 
    #cache = [0]*(size + 1)

    #base case
    cache[0][2] = nums[0]
    #temp = nums[0]
    cache[0][1] = nums[0]

    for i in range(1, size):
        #temp1 = temp
        cache[i][2] = nums[i] #I store the array numbers at index [I][2]
        cache[i][1] = cache[i - 1][0] + nums[I]  #the max sum is store here
        cache[i][0] = max(cache[i - 1][1], cache[i -1][0])   #current sum is store there
    
    maxset = 0
    for i in range(0, size):          #I get the max sum
        if(cache[i][1] > maxset):
            maxset = cache[i][1]

    for i in range(0, size):         #I get the first element here
        if(cache[i][1] == maxset):
            temp = cache[i][2]

    count = 0
    for i in range(0, size): # I check at what index in the nums array the index 'temp' is store
        if(nums[i] != temp):
            count += 1


    if(size - 1 == count):    #iterate through the nums array to apend the non-adjacent elements
        if(count % 2 == 0):
            for i in range(0, size):
                if i % 2 == 0 and i < size:
                    list.append(nums[i])
        else:
            for i in range(0, size):
                if i % 2 != 0 and i < size:
                    list.append(nums[i])

    list[:]= [item for item in list if item >= 0]

    return list


if __name__ == '__main__':

    A = [7,2,-3,5,-4,8,6,3,1]
    B = [7,2,5,8,6]
    C = [-2,3,1,10,3,-7]
'''
Also, I came up with the idea to create another array to store the elements that added to the max sum, but I  don't know how to do that.
Any guidance would be appreciated and thanks beforehand!
dynamic-programming algorithm python
2 Answers

Probably not the best solution , but what about trying with recursion ?

tests = [([7, 2, -3, 5, -4, 8, 6, 3, 1], [7, 5, 8, 3]),
         ([7, 2, 5, 8, 6], [7, 5, 6]),
         ([-2, 3, 1, 10, 3, -7], [3, 10]),
         ([7, 2, 9, 10, 1], [7, 9, 1]),
         ([7, 2, 5, 18, 6], [7, 18]),
         ([7, 20, -3, -5, -4, 8, 60, 3, 1], [20, 60, 1]),
         ([-7, -20, -3, 5, -4, 8, 60, 3, 1], [5, 60, 1])]


def bigest(arr, cache, final=[0]):
  if len(arr) == 0:
    return cache
  for i in range(len(arr)):
    result = bigest(arr[i + 2:], [*cache, arr[i]], final)
    if sum(cache) > sum(final):
      final[:] = cache[:]
    if sum(result) > sum(final):
      final[:] = result[:]
  return result


if __name__ == "__main__":
  print("has started")
  for test, answer in tests:
    final = [0]
    bigest(test, [], final)
    assert final == answer, "not matching"
    print(f"for {test} , answer: {final} ")
user_109729190

Here is a dynamic programming approach.

def best_skips (data):
    answers = []
    for i in range(len(data)):
        x = data[i]
        best = [0, None]
        for prev in answers[0:i-1]:
            if best[0] < prev[0]:
                best = prev

        max_sum, path = best

        answers.append([max_sum + x, [x, path]])

    answers.append([0, None]) # Add empty set as an answer.

    path = max(answers)[1]
    final = []
    while path is not None:
        final.append(path[0])
        path = path[1]
    return final
user_5854110
Related