I was asked this question in first round of onsite interview.
geeksforgeeks.org seems to have almost all of the interview questions I faced. they also write the code in C and show all possible ways of doing the problem. If only I had time to go through their collection of 1000+ interview questions collections before my interviews...
Since this question is also present in http://geeksforgeeks.org/?p=576 I would just give the link to their page. Below is the code which I wrote during interview.
int maxSumSubSequence( int a[] )
{
int maxSum = a[0];
int currentSum = 0;
int alen = sizeof(a)/sizeof(a[0]);
for( int i = 0; i < alen; i++ )
{
currentSum += a[ i ];
if( currentSum > maxSum )
{
maxSum = currentSum ;
}
if( currentSum < 0 )
{
currentSum = 0;
}
}
return maxSum;
}
Test cases: All 0's, all positives, all negatives, mixture of positive and negatives. Major case where this will fail is if the array contains all MaxInts.
time complexity : linear
Subscribe to:
Post Comments (Atom)
2 comments:
The given link looks incorrect. I thing you meant http://geeksforgeeks.org/
@Sandeep Jain: Link Corrected.
Post a Comment