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

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] 我发现上述函数的最大值 returns根据我对算法的解释应该是 4，但在网上我找到的唯一两个答案是 14 和 10。

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

基本上，如果给定 [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]，其中 returns 总和为 14。

请查看下面的内容 link 以便更好地理解：
Kadane Algorithm for maximum sum subarray

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

Need help in Algorithms - Finding the outputted maximum sum

arrays

algorithm

pseudocode

greedy