The best programs are written so that computing machines can perform
them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist
who works with traditional aesthetic and literary forms as well as mathematical concepts, to
communicate the way that an algorithm works and to convince a reader that the results will be correct.
― Donald E. Knuth

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 farint curr_max = 0; // curr_maxint 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;
}
// mainint 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;
}

#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 farint curr_max = 0; // curr_maxint 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;
}
// mainint 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;
}