Thursday, June 24, 2010

Maximum Value Contiguous Subsequence

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

2 comments:

Sandeep Jain said...

The given link looks incorrect. I thing you meant http://geeksforgeeks.org/

Dheeraj Pulluri said...

@Sandeep Jain: Link Corrected.