Problem - Maximum Subarray

Find the contiguous subarray with the largest sum.

Example: [-2,$1$,-3,$4$,-1,$2$,$1$,-5,4]. Answer: $6$ (subarray [4,-1,$2$,1]).

This is classic and has a beautiful greedy solution: Kadane's algorithm. Constraint: $n \le 10^5$. Checking all $O(n^2)$ time using $O(1)$ space subarrays times out. Kadane gives $O(n)$.