Maximum Subarray

The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. Kadane's algorithm provides an efficient dynamic programming approach to solve this problem in O(n) time. It maintains the maximum sum of a subarray ending at the current position and updates the global maximum if the current ending sum exceeds it.

Experiment

You can interact with the Maximum Subarray module to visualize this algorithm:

1. Enter a sequence of integers in the Sequence text input (e.g., -4,-2,-7). Valid inputs are up to 12 comma-separated integers between -9 and 9.
2. Click the Step button to reveal the calculation for the next element in the array. Observe how the Ending Sum and Best Sum update based on Kadane's recurrence relation.
3. Alternatively, click Finish to immediately compute the entire sequence and see the final result. For a sequence of negative numbers like -4,-2,-7, you will see that the maximum subarray is simply the largest single negative number, -2 at index 1.
4. Use the Reset button to rewind the cursor to the beginning and start the execution over with the same sequence.