arrays - 在算法方面需要帮助 - 查找输出的最大总和

Question

我目前正在研究算法，我对一个家庭作业问题感到好奇(是的..我知道)，我一直在寻找相互矛盾的答案。

在伪代码中，算法是:

Algorithm-1(A:array[1..n] of integer) sum,max:integer
sum = 0
max = 0
for i = 1 to n
    sum = 0
    for j = i to n
        sum = sum + A[j]
        if sum > max then
            max = sum
return max

给定数组 [-1,2,-3,4,-5,6,7,-8,9,-10] 我发现上面函数返回的最大值应该是 4算法的解释，但我在网上找到的唯一两个答案是 14 和 10。

我对这个算法的理解是，它获取基本数组，找到它的总和，然后从下一个索引开始获取相同的数组并找到那个总和，返回的值是这些总和中的最高值。

基本上，如果给定 [1,2,-3,4,5] 数组，它会这样看:

[1,2,-3,4,5] 的总和 = 9

[2,-3,4,5] 的总和 = 8

[-3,4,5] 的总和 = 6

[4,5] 的总和 = 9

[5] 的总和 = 5

最后返回的最大值是 9，因为 9 > 8 > 6 > 5

基于这种理解，我认为我的数组的值是 [6,7,-8,9,-10] 子数组中的 4。那是正确的吗？

Answer 1

不，我想你不理解子数组的概念，子数组基本上是数组中任何一组连续的元素。让我们以你的例子为例。

为了

[-1,-2,-3,4,-5,6,7,-8,9,-10]

对于每个大小为 N 的数组，都有 N*(N+1)/2 个子数组。在这种特殊情况下，答案是子数组 [6,7,-8,9]，它返回总和为 14。

请查看以下链接以更好地理解:
Kadane Algorithm for maximum sum subarray