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.