最大求和子数组-返回子数组与求和分治
对于使用分治方法的最大和子数组算法，我需要返回和和子数组。
我能在所有的测试中正确地计算和。然而，我无法计算出正确的子数组。
class Results:
max = 0
maxSubArray = []
start_index = 0
stop_index = 0
def divide_and_conquer(arr, left, right):
res = Results()
maxLeftBorderSum = 0
maxRightBorderSum = 0
leftBorderSum = 0
rightBorderSum = 0
center = (left + right)//2
if left == right:
if(arr[left]>0):
res.max = arr[left]
res.start_index = left
res.stop_index = right
res.maxSubArray = arr[left:right]
return res
else:
res.max = 0
res.start_index = left
res.stop_index = right
res.maxSubArray = arr[:]
return res
maxLeft = divide_and_conquer(arr, left, center)
maxRight = divide_and_conquer(arr, center+1, right)
maxLeftSum = maxLeft.max
maxRightSum = maxRight.max
rightstopindex = 0
leftstartindex = 0
for i in range(center, left-1, -1):
leftBorderSum = leftBorderSum + arr[i]
if leftBorderSum > maxLeftBorderSum:
maxLeftBorderSum = leftBorderSum
leftstartindex = i
for i in range(center+1, right+1):
rightBorderSum = rightBorderSum + arr[i]
if rightBorderSum > maxRightBorderSum:
maxRightBorderSum = rightBorderSum
rightstopindex = i
res.max = max(maxLeftBorderSum + maxRightBorderSum, max(maxRightSum, maxLeftSum))
if res.max == maxLeftBorderSum + maxRightBorderSum:
res.start_index = leftstartindex
res.stop_index = rightstopindex
res.maxSubArray = arr[leftstartindex:rightstopindex]
elif res.max == maxRightSum:
res.start_index = maxRight.start_index
res.stop_index = maxRight.stop_index
res.maxSubArray = arr[maxRight.start_index:maxLeft.stop_index]
else:
res.start_index = maxLeft.start_index
res.stop_index = maxLeft.stop_index
res.maxSubArray = arr[maxLeft.start_index:maxLeft.stop_index]
return res
我的总数（正确）：34
阵列：2 9 8 6 5-11 9-11 7 5-1-8-3 7-2
正确子数组：2 9 8 6 5
我的总数（正确）：50
阵列：31-41 59 26-53 58 97-93-23 84
正确子数组：59 26-53 58 97
我的总数（正确）7
数组：12 99 99-99-27 0 0 0-3 10
正确子数组：12 99 99
我的总数（正确）6
共有1个答案
以下变量需要以不同的方式初始化。因为它们在上面的代码中是零的，所以当数组只包含负数时，它们在循环中有时不会改变。
maxLeftBorderSum = arr[center]
maxRightBorderSum = arr[center+1]
leftstartindex = center
rightstopindex = center+1
-
O(n^2)算法简单。有没有人对此有更好的算法？
-
我试图在一个数组中找到具有最大和的邻接子数组。所以，对于数组 {5,15,-30,10,-5,40,10}
-
我想从数组的一部分找到最大值和最小值。我知道我可以通过复制数组将所需的数组部分复制到另一个数组中，但只是想知道是否可以不复制数组，因为我必须为不同的子数组进行循环 例如： 现在我想从1到4找到子数组的最小/最大值（如果可能，不复制子数组）
-
很抱歉发了这么长的帖子，但我不明白我做错了什么。感谢您事先的帮助！ 这里是当前面提到的列表作为输入给出时的输出，我已经经历并查看了每一个步骤，列表中的每一个消除在我看来都是合乎逻辑的，我不知道一个人怎么会以结束和105结束。如果有人能帮我理解，我会非常感激的！
-
我有一个子阵列： 我想将每个子数组的元素放入另一个数组中，但子数组大小的总和必须小于或等于6。所以我想得到这样的东西 我现在的代码是 我被困在这里，因为我的代码只有两个前元素。原始数组有大约1000个子数组，我的代码没有以那种形式分割它。
-
给定一个正负整数数组，如何找到长度在和之间的最大和子数组（连续子数组）？ 例如：如果数组是 我的方法： 我不太确定如何处理这个问题。我想也许是滑动窗口+Kadane的组合。我听说前缀和+滑动窗口可能是一个可能的解决方案，但我不确定如何实现它。