# Find the contiguous subarray within an array (containing at least one number) which has the largest sum

Interview Q: Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example: Given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

For this problem, return the maximum sum.

My solution (pseudocode and code) is below. Works, but can someone tell me

1. Is there a faster algo?

2. Is the code structure done for an interview?

Pseudocode

//maxTillNow=A
//maxStart=0
//maxLength=1
//Set currIndex =0
//Loop till currIndex == arrayLength
//  Set offset,sum=0
//      If A(currIndex] is -ve, then the only thing you need to do is check if it is > maxTillNow (in case all elements are -ve). If yes, set maxTillNow to A[currIndex] and move on

//      if +ve
//          Look at sums of elements starting at A[currIndex] ... A[currIndex+offset] for offsets in range 0 to currIndex+offset<length
//            if any sum > maxTillNow, store
//            Also find index of first -ve element you encounter as you look at elements A[currIndex+1]... -->firstNegIndex
//            nextElement to look at it firstNegIndex+1


Full code

int maxSubArray(const int* A, int n1) {
int currIndex=0;
int maxSumTillNow=A ;
int maxSumStart=0 ;
int maxSumLength=1 ;
int currLength;
int sum ;
int firstNeg ;

while(currIndex<=n1-1)
{
if(A[currIndex]<0)
{
if(A[currIndex]>maxSumTillNow)
maxSumTillNow=A[currIndex] ;
currIndex++ ;
continue ;
}
sum=0 ;
firstNeg=-1 ;
for(currLength=0;currLength+currIndex<=n1-1;currLength++)
{
sum+=A[currIndex+currLength] ;
if(sum>maxSumTillNow)
{
maxSumTillNow=sum ;
maxSumStart=currIndex ;
maxSumLength=currLength+1 ;
}
if(firstNeg==-1 && A[currIndex+currLength]<0)
{
firstNeg=currIndex+currLength ;
}
}
if(firstNeg==-1)
{
break ;
}
currIndex=firstNeg+1 ;
}
return maxSumTillNow ;

}


I can also get additional info on exact sequence leading to max sum as below

    //    printf("Max sum is = %d, starting at index %d and length =%d\n",maxSumTillNow,maxSumStart,maxSumLength) ;
//    printf("Max sub Array is [") ;
//    for(currIndex=maxSumStart;currIndex<=maxSumStart+maxSumLength-1;currIndex++)
//    {
//        printf("%d,",A[currIndex]) ;
//    }
//    printf("]\n") ;

}

• Does not work if all numbers in array are -ve May 1 '16 at 22:33

1

The usual C coding conventions dictate that a space is added before and after a binary operator. For example, you should write

a += b;
if (foo < bar) ...
int currIndex = 0;


a+=b;
if(foo<bar) ...
int currIndex=0;


Also, you should add a single space before the opening parenthesis associated with keywords for, while, and if. For example, you should write

for (i = 0; i < x; ++i) ...


for(i = 0; i < x; ++i) ...


2

You add a space (sometimes) before the closing semicolon (;). Don't do it.

3

Your code would be more nifty if you added an empty line after each closing brace (}). For example,

if (sum > maxSumTillNow)
{
...
}

if (firstNeg == -1 && A[currIndex + currLength] < 0)
{
...
}


4

Summa summarum

All in all, I had this in mind:

#include <stdio.h>
#define MAX(a, b) (a) > (b) ? (a) : (b)

int maxSubArray(const int* A, int n1)
{
int currIndex     = 0;
int maxSumTillNow = A;
int maxSumStart   = 0;
int maxSumLength  = 1;
int currLength;
int sum;
int firstNeg;

while (currIndex <= n1 - 1)
{
if(A[currIndex] < 0)
{
if(A[currIndex] > maxSumTillNow)
{
maxSumTillNow = A[currIndex];
}

currIndex++;
continue;
}

sum = 0;
firstNeg = -1;

for (currLength = 0; currLength + currIndex <= n1 - 1; currLength++)
{
sum += A[currIndex+currLength];

if (sum > maxSumTillNow)
{
maxSumTillNow = sum;
maxSumStart   = currIndex;
maxSumLength  = currLength + 1;
}

if (firstNeg == -1 && A[currIndex + currLength] < 0)
{
firstNeg = currIndex+currLength;
}
}

if(firstNeg == -1)
{
break ;
}

currIndex = firstNeg + 1;
}

return maxSumTillNow;
}

int kadanesAlgorithm(const int* array, const size_t length)
{
int maximum_so_far = array;
int maximum_end    = array;

for (size_t index = 1; index < length; ++index)
{
const int x    = array[index];
maximum_end    = MAX(maximum_end + x, x);
maximum_so_far = MAX(maximum_end, maximum_so_far);
}

return maximum_so_far;
}

int main(int argc, const char * argv[]) {
int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
printf("Original result: %d\n", maxSubArray(arr, 9));