See On Github

Wikipedia Description

In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values 2, 1, 3, 4, 1, 2, 1, 5, 4; the contiguous subarray with the largest sum is 4, 1, 2, 1, with sum 6.The problem was first posed by Ulf Grenander of Brown University in 1977, as a simplified model for maximum likelihood estimation of patterns in digitized images. A linear time algorithm was found soon afterwards by Jay Kadane of Carnegie-Mellon University (Bentley 1984).Kadane's algorithm consists of a scan through the array values, computing at each position the maximum (positive sum) subarray ending at that position. This subarray is either empty (in which case its sum is zero) or consists of one more element than the maximum subarray ending at the previous position. The algorithm only needs to keep track of the ending position because the implied starting position is just after the last position the sum went negative, and you can always get a higher sum by dropping any negative-sum prefix. Thus, the problem can be solved with the following code, expressed here in Python: https://en.wikipedia.org/wiki/Maximum_subarray_p...

Implementations