Find sum of largest subset of array

3
votes

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.

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.

Thanks in advance.

1
arraysdynamic-programming

1 Answers

3
votes

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