查找数组最大子集的总和 [英] Find sum of largest subset of array

问题描述

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

I'm solving one CS problem, namely we have given array with size N, such that N<=100000, and the array will have both negative and positive integers, now we have to find the sum of the largest subset of the array, or more formally we have to find the indexes i and j such that the sum of the elements between those elements will me maximum possible.

这里是一个示例：
N = 5，array = {12，-4，-10，4，9}，答案= 13，因为4 + 9是我们可以获得的最佳结果。

Here is one example: N=5, array={12, -4, -10, 4, 9}, answer = 13, because 4+9 is the best we can get.

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

I know that this can be solved by bruteforce in quadratic time, but I wonder if this can be solved in linear, on logarithmic time.

在此先感谢。

推荐答案

根据此演示文稿，该算法由 Kadane 显然是ds线性运行时边界；从那里获取的C ++实现如下所示。

According to this presentation, the algorithm by Kadane apparently yields a linear runtime bound; an implementation in C++ taken from there looks as follows.

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

这篇关于查找数组最大子集的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！