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

Question

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[0] //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[0] ; 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") ; } 

Answer 1

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; 

instead of

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) ... 

instead of

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

Your algorithm seems to run in quadratic time. The Kadane's algorithm does this in linear time.

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[0]; 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[0]; int maximum_end = array[0]; 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)); printf("Kadane's result: %d\n", kadanesAlgorithm(arr, 9)); } 

Hope that helps.