Question 96
Which algorithm finds the maximum sum of a contiguous subarray in linear time?
Kadane's algorithm maintains the best subarray ending at the current position and the best overall sum. At each element it decides whether to extend the previous subarray or start anew.