Maximum Subarray
Find the contiguous subarray with the largest sum and return that sum.
A way to picture it
A snowball rolls down a hill of numbers, picking up each one it passes. If the snowball ever turns negative, it's only dragging you down, so you drop it and start a fresh one right there.
How to approach it
Kadane's algorithm: at each number, either extend the current run or start fresh — whichever is bigger. The best run you ever see is the answer.
Example
Input: {"nums":[null,1,null,4,null,2,1,null,4]}. Output: 6.
Complexity: O(n) time and O(1) space. One pass, two running values.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.