CODEWITHSUNDEEP
algorithm
siva
siva

Reputation: 1731

How to find the maximum contiguous SUM in an array (which contains positive and negative numbers)?

I want to write a function ContigSum(i,j) that calculates the sum of the contiguous elements a[i] through a[j], where i<=j and a[] contains positive and negative numbers.

Could you please tell me a time efficient solution to find maximized contiguous SUM in the array?

Upvotes: 1

Views: 6652

Answers (7)

satnam
satnam

Reputation: 1425

Here is my solution in Ruby. Return the maximum contiguous subsum in O(n) time and O(1) memory. I also, wrote some unit tests just in case ;)

def largest_contiguous_subsum(array)
  max_sum = 0
  current_sum = 0
  array.each do |num|
    current_sum += num
    max_sum = current_sum if current_sum >= max_sum
    current_sum = 0 if current_sum < 0
  end

  return max_sum
end

Upvotes: 0

farhangdon
farhangdon

Reputation: 2003

Here is the C++ Code I just implemented and tested on Visual Studio 2012.

int maxSum(int *A, int lo, int hi)  {
    int left = lo, right = lo, sum = INT_MIN, currentMaxSum = 0, maxLeft = lo, maxRight = lo;
    for(int i = lo; i < hi; i++)    {
        currentMaxSum += A[i];
        if(currentMaxSum > sum) {
            sum = currentMaxSum;
            right = i;
            maxLeft = left;
            maxRight = right;
        }
        if(currentMaxSum < 0)   {
            left = i+1;
            right = left;
            currentMaxSum = 0;
        }
    }
    printf("Maximum sum contiguous subarray :");
    for(int i = maxLeft; i <= maxRight; i++)
        printf(" %d", A[i]);
    printf("\n");
    return sum;
}

Below is the main() code to call the above function.

int main()  {
    int A[] = {3,-4, -3, 2, 6};
    int N = sizeof(A) / sizeof(int);

    printf("Maximum sum : %d\n", maxSum(A, 0, N));

    return 0;
}

Upvotes: 0

Shiwakant Bharti
Shiwakant Bharti

Reputation: 382

This is the correct Java Code which will handle scenarios including all negative numbers.

    public static long[] leftToISumMaximize(int N, long[] D) {
        long[] result = new long[N];
        result[0] = D[0];
        long currMax = D[0];
        for (int i = 1; i < N; i++) {
            currMax = Math.max(D[i], currMax + D[i]);
            result[i] = Math.max(result[i - 1], currMax);
        }
        return result;
    }

Upvotes: 0

Navneet Verma
Navneet Verma

Reputation: 1

static void MaxContiguousSum(int[] x, int lb, int[] result)
{
    int start, end, sum, testSum;

    start = lb;
    end = lb;

    /* Empty vector has 0 sum*/
    sum = 0;

    testSum = 0;
    for (int i=lb; i < x.length; i++)
    {
        if (sum + x[i] < 0)
        {
            /* Net contribution by current term is negative. So, contiguous sum lies in [start,i-1] 
              or [i+1, array upper bound]*/
            MaxContiguousSum(x, i+1, result);

            if (result[0] < sum)
            {
                result[0] = sum;
                result[1] = start;
                result[2] = end;
            }
            return;

        }
        else
        {
            testSum += x[i];

            if (testSum > 0)
            {
                /* Move the end marker since incrementing range is beneficial. */
                end = i;

                /* update the sum*/
                sum += testSum;

                /* reset the testSum */
                testSum = 0;
            }
        }

    }

    /* Update the results */
    result[0] = sum;
    result[1] = start;
    result[2] = end;

    return;


}

Upvotes: 0

Monish
Monish

Reputation: 11

Alex, you have a very elegant algorithm but it needs correction for an array that contains a single element that is negative.

Of course, in the original algorithm of Kadane's, one can get the subarray start and end indexes which is useful for knowing the "path".

Here's an inelegant but I think correct Python function:

def max_subarray(A):
    (maxSum, maxStartIndex, maxEndIndex) = (float("-inf"), 0, 0)
    (currentMaxSum,currentStartIndex,currentEndIndex ) = (0,0,0)

    for item in A: 
        currentMaxSum = currentMaxSum + item
        if currentMaxSum > maxSum :
            (maxSum, maxStartIndex, maxEndIndex) = (currentMaxSum, currentStartIndex, currentEndIndex)
        if currentMaxSum < 0 :
            currentMaxSum = 0
            currentStartIndex = currentEndIndex + 1

        # continue here.
        currentEndIndex = currentEndIndex + 1

    return (maxSum, maxStartIndex, maxEndIndex)

Upvotes: 1

Alex Martelli
Alex Martelli

Reputation: 882591

Well explained in the wikipedia entry about the subject. I find the Python code (i.e., executable pseudocode) they give for Kandane's Algorithm to be a little gem:

def max_subarray(A):
    max_so_far = max_ending_here = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Upvotes: 7

Jonathan Leffler
Jonathan Leffler

Reputation: 754900

This is discussed in Column 7 of the 1st Edition or Column 8 of the 2nd Edition of 'Programming Pearls' by Jon Bentley.

Upvotes: 2

Related Questions