# Arrays - Contiguous subarray with maximum sum

**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.

/** * @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