53. Maximum Subarray

How to solve Maximum Subarray (LeetCode 53): the approach in brief

The problem

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Pattern

Maximum Subarray is a Dynamic Programming (DP) Patterns problem, in the 1D Array (Kadane's Algorithm for Max/Min Subarray) subpattern. The pattern covers fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break

Master Kadane's algorithm for finding maximum (or minimum) subarray sum in O(n) time.

Approach outline

1. Think about how you can use dynamic programming to keep track of the best solution up to each index in the array.
2. Consider maintaining a running sum that represents the maximum subarray sum ending at the current position, and decide whether to extend the previous subarray or start fresh at the current element.
3. How can you update a global maximum as you iterate through the array to ensure you capture the largest subarray sum found so far?

Complexity

The reference solution runs in O(n) time and O(1) space.

Asked at

Maximum Subarray has been reported in interviews at Adobe, Amazon, Apple, Bloomberg, ByteDance, Cisco, Facebook, Google.