Kadanes

Kadane's algorithm is a dynamic programming technique for finding the maximum sum of a contiguous subarray within a one-dimensional array of numbers. It answers the common maximum subarray problem, which seeks the largest possible sum that can be obtained by summing a consecutive block of elements.

The standard approach processes the array from left to right while maintaining two values: the best sum that ends at the current position (current) and the best sum found so far (best). For each element x, current is updated to the maximum of x and current plus x, and best is updated to the maximum of best and current. This yields a linear time solution with constant extra space, specifically O(n) time and O(1) space.

Implementation notes include handling all-negative arrays. By initializing current and best with the first element (or by ensuring the update rules allow negative values), Kadane's algorithm returns the largest (least negative) single element when no positive-sum subarray exists. It can also be augmented to track the start and end indices of the subarray providing the maximum sum.

Extensions of the idea include variations that return the indices, handle ties, or adapt to two-dimensional arrays (the 2D Kadane algorithm). In 2D, the method is combined with a variant of the 1D Kadane applied across rows to find a maximum sum submatrix.

Applications span finance, data analysis, signal processing, and pattern recognition, where identifying the most significant consecutive segment of data is useful. Historically, the algorithm is attributed to Jay Kadane, who described it in the 1980s; it remains a foundational technique in algorithm design and dynamic programming.