Maximum Subarray Comparison Lab
Find a nonempty contiguous subarray with maximum sum using incremental brute force, divide and conquer, or Kadane’s algorithm. Inspect candidate intervals, recursive calls, and running sums. All three use the same tie rule: earliest start, then earliest end.
Apply array after editing. Changing the algorithm replays the same array. One Step is an addition, call/split, return, or result decision—not a fixed amount of CPU time.
Current interval and action
Recursive call stack · bottom → top
Complete-run comparison for this array
| Algorithm | Growth | Element-sum additions | Maximum sum | Interval |
|---|
This table summarizes completed executions on the current input, independently of playback. Counts include only additions used to form element sums, including left-sum + right-sum in divide and conquer. Comparisons, recursion, assignments, and initialization are excluded, so these counts are not total runtime.
Reading the three approaches
- Brute force: choose each start index and extend a running sum through every possible end.
- Divide and conquer: solve the left and right halves, scan a suffix and prefix to form the best crossing interval, then choose among the three results.
- Kadane: the best interval ending here either extends the previous interval or starts at this element.
The answer must contain at least one element. An all-negative input therefore returns its largest element, not an empty interval with sum zero.