arrays - 求数组最大子集的和

Question

我正在解决一个CS问题，即我们给定了一个大小为N的数组，使得N<=100000，并且该数组将同时具有负整数和正整数，现在我们必须找到最大子集的和数组，或者更正式地说，我们必须找到索引 i 和 j，以便这些元素之间的元素之和达到最大可能。

这是一个例子:N=5，array={12, -4, -10, 4, 9}，answer = 13，因为4+9是我们能得到的最好结果。

我知道这可以通过暴力破解在二次时间内解决，但我想知道这是否可以在线性、对数时间内解决。

提前致谢。

Answer 1

根据this演示，算法由 Kadane显然产生了线性运行时间界限；从那里获取的 C++ 实现如下所示。

int maxSubArraySum(int a[], int size)
{
    int max_so_far = INT_MIN, max_ending_here = 0;

    for (int i = 0; i < size; i++)
    {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;

        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}