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

# Algorithms

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