arrays - 查找数组中元素的最大总和

Question

编写一个程序，通过给定的整数值数组（包含负整数）找到数组中连续元素的最大和。

例子：

2、3、-6、-1、2、-1、6、4、-8、8

给

11

我正在寻找比 O(N^2) 更快的解决方案。

Answer 1

我认为Kadane 的算法是你想要的

Answer 2

这实际上是我在大学学习的教科书问题（Mark Allen Weiss 在 C 中的数据结构和算法）......这是一个非常漂亮和优雅的解决方案，并且在 O(N) 中解决

int MaxSubsequenceSum(int A[])
{
    int sum = 0, maxSum = 0;

    for (int j = 0; j < A.Length; j++)
    {
        sum = sum + A[j];

        if (sum > maxSum)
            maxSum = sum ;
        else if (sum < 0)
            sum = 0;
    }
    return maxSum;
}

Answer 3

您可以首先按降序对给定数组进行排序，然后将数组的前三个元素通过 : sum=arr[0]+arr[1]+arr[2] 初始化sum=0并打印总和来求和。