Maximum Subarray

Worked Example

Consider the sequence of integers: -2, 3, -1, 4, -5. Let's trace Kadane's algorithm step-by-step.

1. Index 0 (Value: -2): The subarray ending here can only be [-2]. Ending sum = -2 (Start: 0). Best sum so far = -2 (Range: 0..0).
2. Index 1 (Value: 3): We can extend the previous subarray or start fresh. Extending: -2 + 3 = 1. Starting fresh: 3. Since 3 > 1, we start fresh. Ending sum = 3 (Start: 1). Since 3 > -2, Best sum = 3 (Range: 1..1).
3. Index 2 (Value: -1):Extending: 3 + (-1) = 2. Starting fresh: -1. Since 2 > -1, we extend. Ending sum = 2 (Start: 1). Best sum remains 3 (Range: 1..1).
4. Index 3 (Value: 4):Extending: 2 + 4 = 6. Starting fresh: 4. Since 6 > 4, we extend. Ending sum = 6 (Start: 1). Since 6 > 3, Best sum = 6 (Range: 1..3).
5. Index 4 (Value: -5):Extending: 6 + (-5) = 1. Starting fresh: -5. Since 1 > -5, we extend. Ending sum = 1 (Start: 1). Best sum remains 6 (Range: 1..3).

The final best sum is 6, corresponding to the subarray from index 1 to 3 with values [3, -1, 4].

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.

Limitations

Kadane's algorithm natively finds the maximum contiguous subarray. Our implementation guarantees that it finds at least a single element (it does not return an empty subarray with sum 0 for an all-negative input array). The time complexity is O(n) making it extremely efficient for large datasets, and its mathematical recurrence can stream one value at a time; this bounded teaching view stores the input and completed trace. Empty input explicitly has no nonempty subarray, rather than a numeric answer 0. The visualization restricts inputs to small arrays (up to 12 elements with values between -9 and 9) to fit within a bounded, readable trace table, though the underlying algorithm can handle much larger datasets. Note that when there are ties for the maximum sum, our implementation adheres strictly to a tie-breaking rule of preferring the earliest start index, and then the earliest end index.

References

For further reading on the analysis and proofs behind this algorithm:

• Takaoka: Efficient Algorithms for the Maximum Subarray Problem - A primary paper on the maximum-subarray objective and its higher-dimensional generalization. Its review of the one-dimensional problem gives the linear recurrence; the small integer trace and tie convention here are our own worked experiment.