时间戳

首页 > 解决方案 > 在算法中需要帮助 - 找到输出的最大和

arrays - 在算法中需要帮助 - 找到输出的最大和

问题描述

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

在伪代码中，算法是：

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] 根据我对算法，但在网上我找到的唯一两个答案是 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 。那会是正确的吗？

标签： arraysalgorithmpseudocodegreedy

解决方案

不，我想您不了解子数组的概念，子数组基本上是数组中的任何一组连续元素。让我们举个例子。

为了

[-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

推荐阅读