Arrays & Strings

Problem
Find the largest sum contiguous subarray.
Given an array of positive and negative integers, find a contiguous subarray whose sum (sum of elements) is maximum. We are interested only in the maximum sum.
For e.g, Consider the array { 2,-4, 3, -2, 6, -9, 5 } .
Largest sum contiguous subarray is { 3, -2, 6 } & the sum is 7.
There is no other contiguous subarray with sum > 7.

Solution
Maintain two variables prev_max and curr_max, both initialized to 0.
Update prev_max & curr_max as you iterate over the array.
For i = 0 … n-1, curr_max = curr_max + 1, if arr(i) is positive & curr_max = 0, if arr(i) is negative.
Update prev_max whenever curr_max > prev_max.
See the implementation below.

```#include<iostream>
using namespace std;

// find the largest sum of contiguous subarray elements
int findLargetSumSubarray(int arr[],int size) {
int prev_max = 0; // max sum so far
int curr_max = 0; // curr_max
int i;
int j=0,k=0;
for (i=0;i<size;i++) {
curr_max += arr[i];
if (curr_max < 0) {
// if sum becomes (-)ve, change it to zero
curr_max = 0;
}
else if (prev_max < curr_max) {
// if sum becomes greater than the max sum
// so far update it
prev_max = curr_max;
}
}
return prev_max;
}

// main
int main() {
int arr[] = { 1,4,-6,6,-4,7,1,3,-2,1 };
int size = sizeof(arr)/sizeof(arr[0]);
int largest_sum = findLargetSumSubarray(arr,size);
cout<<"\nLargest :: "<<largest_sum;
cout<<endl;
return 0;
}```