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
Is there a faster algo?
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") ;
}