# Largest Sum Contiguous Subarray (Another Approach)

Hello Everyone,

Write an efficient program to find the sum of contiguous subarray within a one-dimensional array of numbers that has the largest sum.

Another approach:

`int` `maxSubarraySum(` `int` `arr[], ` `int` `size)`

`{`

` ` `int` `max_ending_here = 0, max_so_far = INT_MIN;`

` ` `for` `(` `int` `i = 0; i < size; i++) {`

` `

` ` `// include current element to previous subarray only`

` ` `// when it can add to a bigger number than itself.`

` ` `if` `(arr[i] <= max_ending_here + arr[i]) {`

` ` `max_ending_here += arr[i];`

` ` `}`

` `

` ` `// Else start the max subarry from current element`

` ` `else` `{`

` ` `max_ending_here = arr[i];`

` ` `}`

` ` `if` `(max_ending_here > max_so_far)`

` ` `max_so_far = max_ending_here;`

` ` `}`

` ` `return` `max_so_far;`

`} ` `// contributed by Vipul Raj`

Time Complexity: O(n)

Algorithmic Paradigm: Dynamic Programming
Following is another simple implementation suggested by Mohit Kumar. The implementation handles the case when all numbers in the array are negative.

`#include<iostream>`

`using` `namespace` `std;`

`int` `maxSubArraySum(` `int` `a[], ` `int` `size)`

`{`

` ` `int` `max_so_far = a[0];`

` ` `int` `curr_max = a[0];`

` ` `for` `(` `int` `i = 1; i < size; i++)`

` ` `{`

` ` `curr_max = max(a[i], curr_max+a[i]);`

` ` `max_so_far = max(max_so_far, curr_max);`

` ` `}`

` ` `return` `max_so_far;`

`}`

`/* Driver program to test maxSubArraySum */`

`int` `main()`

`{`

` ` `int` `a[] = {-2, -3, 4, -1, -2, 1, 5, -3};`

` ` `int` `n = ` `sizeof` `(a)/` `sizeof` `(a[0]);`

` ` `int` `max_sum = maxSubArraySum(a, n);`

` ` `cout << ` `"Maximum contiguous sum is "` `<< max_sum;`

` ` `return` `0;`

`}`

Output:

Maximum contiguous sum is 7

To print the subarray with the maximum sum, we maintain indices whenever we get the maximum sum.

`// C++ program to print largest contiguous array sum`

`#include<iostream>`

`#include<climits>`

`using` `namespace` `std;`

`int` `maxSubArraySum(` `int` `a[], ` `int` `size)`

`{`

` ` `int` `max_so_far = INT_MIN, max_ending_here = 0,`

` ` `start =0, end = 0, s=0;`

` ` `for` `(` `int` `i=0; i< size; i++ )`

` ` `{`

` ` `max_ending_here += a[i];`

` ` `if` `(max_so_far < max_ending_here)`

` ` `{`

` ` `max_so_far = max_ending_here;`

` ` `start = s;`

` ` `end = i;`

` ` `}`

` ` `if` `(max_ending_here < 0)`

` ` `{`

` ` `max_ending_here = 0;`

` ` `s = i + 1;`

` ` `}`

` ` `}`

` ` `cout << ` `"Maximum contiguous sum is "`

` ` `<< max_so_far << endl;`

` ` `cout << ` `"Starting index "` `<< start`

` ` `<< endl << ` `"Ending index "` `<< end << endl;`

`}`

`/*Driver program to test maxSubArraySum*/`

`int` `main()`

`{`

` ` `int` `a[] = {-2, -3, 4, -1, -2, 1, 5, -3};`

` ` `int` `n = ` `sizeof` `(a)/` `sizeof` `(a[0]);`

` ` `int` `max_sum = maxSubArraySum(a, n);`

` ` `return` `0;`

`}`

Output:

Maximum contiguous sum is 7 Starting index 2 Ending index 6

Time Complexity: O(n)

Auxiliary Space: O(1)