Sub-Array with the Largest Sum

Question of the day :

You are given an array with integers (both positive and negative) in any random order. Find the sub-array with the largest sum. Obviously optimized solution …

 

Solution:

The idea is to keep scanning through the array and calculating the maximum sub-array that ends at every position. The sub-array will either contain a range of numbers if the array has intermixed positive and negative values, or it will contain the least negative value if the array has only negative values.


#include <stdio.h>

void MaxSumSubArray( int *array, int len, int *start, int *end, int *maxSum )
{
 int maxSumSoFar = -2147483648;
 int curSum = 0;
 int a, b, s, i;

a = b = s = i = 0;

for ( i = 0; i < len; i++ )
 {
 curSum += array[i];

 if ( curSum > maxSumSoFar )
 {
 maxSumSoFar = curSum;
 a = s;
 b = i;
 }

 if( curSum < 0 )
 {
 curSum = 0;
 s = i + 1;
 }
 }

*start = a;
 *end = b;
 *maxSum = maxSumSoFar;
}

int main (void)
{
 int arr[] = { -5, 4, -9, 2, 3, -8, 1};
 int start, end, maxsum;

maxSumSubArray (arr, 7, &start, &end, &maxsum);

printf ("\nstart = %d, end = %d, MaxSum = %d\n", start, end, maxsum);
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s