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") ;
 }

• Smart Home: Does not work if all numbers in array are -ve

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.

• Smart Home: Does not work if all numbers in array are negative.
• Smart Home: To make it work for the case where all numbers in array are -ve, change the maximum_end = MAX(maximum_end + x, 0); with maximum_end = MAX(maximum_end + x, x);
• coderodde: @SmartHome Overlooked that, thanks! Updated the code.
• coderodde: @SmartHome On the second thought, if all the integers in the array are negative, you could think that an empty subarray (with the value of 0) is the maximum subarray. What would be your opinion on that issue?
• Smart Home: Thanks, accepted the answer. I guess how to deal with all -ve will depend on use-case. In the case of interview, best approach is to ask the interviewer!