Arrays - Contiguous subarray with maximum sum

0 users say they have been asked this quesiton in interview.
Difficulty Level:

Problem Statement:

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

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.

Solution:
/**
 * @input A : Read only ( DON'T MODIFY ) Integer array
 * @input n1 : Integer array's ( A ) length
 * 
 * @Output Integer
 */
int maxSubArray(const int* A, int n1) {
   int max_so_far = INT_MIN, max_ending_here = 0;
   int i;
   
   for(i = 0; i < n1; i++) {
     max_ending_here = max_ending_here + A[i];
     if(max_so_far < max_ending_here)
        max_so_far = max_ending_here;
     if(max_ending_here < 0)
        max_ending_here = 0;
    }
    
    return max_so_far;
    
}

comments powered by Disqus