Kadane’s Algorithm

Kadane's algorithm is a brilliant and efficient dynamic programming approach to solve the 'maximum subarray problem'. The problem asks to find the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence `[-2, 1, -3, 4, -1, 2, 1, -5, 4]`, the contiguous subarray with the largest sum is `[4, -1, 2, 1]`, with a sum of 6. The naive solution would be to check every possible subarray, which would take O(n^2) time. Kadane's algorithm solves this in O(n) time and O(1) space. The algorithm iterates through the array, keeping track of two variables: `max_so_far` and `max_ending_here`. `max_so_far` stores the maximum sum found anywhere in the array up to the current position, and it will be our final answer. `max_ending_here` stores the maximum sum of a subarray that ends at the current position. For each element, we update `max_ending_here` by adding the current element to it. If `max_ending_here` becomes negative at any point, we reset it to 0, as a negative-sum subarray is not a useful prefix for any future subarray. After updating `max_ending_here`, we compare it with `max_so_far` and update `max_so_far` if needed. This simple logic elegantly handles arrays with all negative numbers as well (with a small modification to initialize `max_so_far` to the first element).