找到数组的最大子集和

Question

我正在解决一个计算机科学问题，给定大小为N的数组，其中N≤100000，并且该数组将包含负数和正数整数。现在我们需要找到最大子集的总和，或更正式地说，我们需要找到索引i和j，使得这些元素之间的元素之和尽可能大。

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

我知道可以通过暴力法在二次时间内解决此问题，但我想知道是否可以在线性或对数时间内解决此问题。

提前感谢您。

- someone12321

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;
}

- Codor