Python：最大子数组和
def maxSequence(arr): #Latest attempt, some issue.
old_arr = []
print(arr)
while old_arr != arr:
old_arr = arr
if arr[0] > 0 and arr[len(arr)-1] > 0: #For when both sides are positive, need to be sure there is not anything to be gained by eliminating some side section
new_sum = 0
y=0
while new_sum >= 0 and y != -1:
new_sum = sum(arr[:y])
y=y+1
if y == len(arr)-1:
y=-1
if y != -1:
arr = arr[y-1:]
print("left %s" %(new_sum))
print("left %s" % (arr))
new_sum = 0
y = 0
while new_sum >= 0 and y != -1:
new_sum=sum(arr[(len(arr)-y):])
y=y+1
if y == len(arr)-1:
y=-1
if y != -1:
arr = arr[:len(arr)-y+1]
print("right %s" %(new_sum))
print("right %s" % (arr))
else:
while arr[0] < 0 or arr[len(arr)-1] < 0: #To eliminate negatives on sides
if arr[0] < 0:
arr = arr[1:]
if arr[len(arr)-1] < 0:
arr = arr[:len(arr)-1]
print("negative %s" % (arr))
print(arr)
print(sum(arr))
[26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17, -26]
[21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
很抱歉发了这么长的帖子，但我不明白我做错了什么。感谢您事先的帮助！
这里是当前面提到的列表作为输入给出时的输出，我已经经历并查看了每一个步骤，列表中的每一个消除在我看来都是合乎逻辑的，我不知道一个人怎么会以结束和105结束。如果有人能帮我理解，我会非常感激的！
[26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25,
-27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10,
-25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17, -26]
negative [26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25,
-8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28,
11, 6, -10, -25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17]
left -22
left [-2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15,
-29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27,
-18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17]
right -8
right [-2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15,
-29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27,
-18, 6, -13, -13, 25, -22, 8, 9, -4]
negative [3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15,
-29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27,
-18, 6, -13, -13, 25, -22, 8, 9]
left -3
left [-5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11,
-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6,
-13, -13, 25, -22, 8, 9]
right -5
right [-5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11,
-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6,
-13, -13, 25]
negative [15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11,
-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6,
-13, -13, 25]
left -5
left [-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27,
-18, 6, -13, -13, 25]
right -1
right [-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27,
-18, 6]
negative [1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18,
6]
left -13
left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6]
right -12
right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27]
left 84
left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27]
right -8
right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
left 77
left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
right 53
right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
[21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
94
共有1个答案
我会用一个小例子来演示你的算法有什么问题。
假设输入是
[2, -3, 1]
[2]显然是最大的子数组。不过，你的算法会看这部分：
[2, -3, 1]
^^^^^
-
我试图在一个数组中找到具有最大和的邻接子数组。所以，对于数组 {5,15,-30,10,-5,40,10}
-
给出了一个由N个整数组成的数组。 数组的最大和是该数组的非空连续子数组的元素的最大和。 例如，数组[1,-2,3,-2,5]的最大和是6，因为子数组[3,-2,5]的和是6，并且不可能实现更大的子数组和。 现在，您只能从给定数组中删除一个以上的元素。这样做可以得到的结果数组的最大可能最大和是多少？ 我正在用我自己的测试用例测试我的代码。我在Dev-C++上得到了正确的输出。但是当我在网上测试我的代
-
我在读“算法导论”。在最大子数组问题（第4章）中，作者提出不能仅仅通过求子数组的最大值和最小值来计算股票买卖的最大利润。作者通过计算所有可能的买进和卖出日期的组合来谈到替代方案，例如蛮力，这将需要0(n^2)个时间。另一种选择是寻找价格日变化数组的最大子数组。 然而，我编写了一个算法，它将花费0(n)个时间，并找到最大利润。这是在0(n)对0(nlogn)的最大子数组问题。但我知道作者不会错的。我
-
NowCoder 题目描述 {6, -3, -2, 7, -15, 1, 2, 2}，连续子数组的最大和为 8（从第 0 个开始，到第 3 个为止）。 解题思路 // java public int FindGreatestSumOfSubArray(int[] nums) { if (nums == null || nums.length == 0) return 0;
-
现在我用不同的测试场景测试它，总是比Kadena的结果更好。我不相信这样的运气，但找不到我错过了什么。你能看看这是否是一个有效的解决方案吗？ 更新代码的思想是只跟踪一个子数组，并添加到其尾数，当数字很低时，和成为尾数组后的负集开始。另外，一开始的负面项目被忽略了。子数组的头只是向前移动。每次sum看起来是maximal-maxsum并且限制被更新。