Find the sum of the largest subset of an array

I solve one problem with CS, that is, we have given an array with size N so that N <= 100000 and the array will have both negative and positive integers, now we need to find the sum of the largest subset of the array, or more formally we have to find the indices i and j so that the sum of the elements between these elements is as large as possible.

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

I know it can be solved with brute force in quadratic time, but I am wondering if this can be solved in linear mode in logarithmic time.

Thanks in advance.

+3


source to share


1 answer


According to this presentation, the Kadane algorithm obviously gives a linear runtime bound; the implementation in C ++, taken from there, looks like this.



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

      

+3


source







All Articles