Sub-Array with the Largest Sum

Question: 

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

.

.

C

A

P

T

A

I

N

I

N

T

E

R

V

I

E

W

.

.

Solution: This is an all-time favorite software interview question. The best way to solve this puzzle is to use Kadane’s algorithm which runs in O(n) time. 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. Here’s some code to illustrate.

void maxSumSubArray( int *array, int len, int *start, int *end, int *maxSum )
{
    int maxSumSoFar = -2147483648;
    int curSum = 0;
    int 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;
}

Think you have a better solution? We’d love to read your comments!

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s