I'm working on a Python assignment where I need to write a program that returns a list of integers representing the largest sum of non-consecutive values from an original list. If the numbers are negative, they should be skipped. I have managed to retrieve the maximum sum, but I'm stuck on how to actually store the values that make up this sum in a list. Here's my current function:
def setmax(nums, n, memo, store):
if n-1 == 0:
return nums[n-1]
elif n-2 == 0 and nums[0] >= nums[1]:
return nums[n-2]
elif n-2 == 0:
return nums[n-1]
else:
memo[n] = max(setmax(nums, n-2, memo, store) + nums[n-1], setmax(nums, n-1, memo, store))
return memo[n]
def max_independent_set(nums):
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
if n == 2:
return max(nums[0], nums[1])
store = []
memo = []
for y in range(n+1):
memo.append(-1)
return setmax(nums, n, memo, store)
2 Answers
It seems like the return statement in your setmax function gives a list with one element, which isn't quite what you want. Are you sure the assignment is asking for a single-element list?
Could you share some example inputs and expected outputs? It’ll help us understand the problem better!
Here are a few test cases:
1. For input: [7,2,5,8,6], the expected output is [7,5,6] which sums to 18.
2. For input: [-1, -1, 0], the output could be [] or [0].
3. For input: [10, 3, 3, 10], the expected output is [10, 10].
You could also try this input: [-1,-1,-10,-34] which should return [].
And for [10, -3, 0], it should give you [10].
Yes, I'm trying to ensure that each individual element of the largest sum is added to a list, like when I input [10,3,3,10] which should return [10, 10].