AlgoViz

Back to All Questions
Maximum Subarray
Amazon
Array
Dynamic Programming

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum, and return its sum.

Example:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Solution Walkthrough

This is solved with Kadane's Algorithm, a classic dynamic programming pattern: at every index, decide whether to extend the previous subarray or start a brand new one from the current element.

  1. Keep two running values: currentSum (the best sum of a subarray ending exactly at the current index) and maxSum (the best sum seen anywhere so far).
  2. Initialize both to nums[0].
  3. For every subsequent element num: set currentSum = Math.max(num, currentSum + num). This is the key decision — if extending the running subarray would make things worse than starting fresh at num, start fresh.
  4. Update maxSum = Math.max(maxSum, currentSum) after every step.
  5. Return maxSum once the array is exhausted.

Because each element is visited exactly once with constant work per element, this runs in O(n) time and O(1) space — a huge improvement over the naive O(n²) approach of checking every subarray.

1
2
3
4
5
6
7
8
9
10
11
12