我是python动态编程的新手，这是我到目前为止所做的代码，用于从数组中获得最大和的数字。然而，我的代码不能为输入数组A工作以下是一些例子:
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]
我的输出适用于B和C，但不适用数组a。我得到的输出是这样的:[1] 7日6日
下面是我的代码: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!
可能不是最好的解决方案，但是尝试递归如何?
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} ")
这是一个动态规划方法。
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