Maximum Subarray is the #13 most asked LeetCode problem globally — and the most elegant introduction to Dynamic Programming as a technique.
Our analysis of 10,385 verified interview questions across 259 companies shows it appeared 66 times across 23 companies — including Google, Amazon, Meta, Microsoft, Goldman Sachs, Bloomberg, LinkedIn, DE Shaw, and J.P. Morgan.
Kadane's Algorithm solves this in O(n) time and O(1) space with a deceptively simple idea: at each position, decide whether to extend the current subarray or start fresh. The decision rule is just one line. Know it cold.
| Metric | Value |
|---|---|
| Total Interview Appearances | 66 verified mentions |
| Companies That Ask It | 23 companies |
| Global Rank | #13 out of 10,385 questions |
| Difficulty | Medium |
| Core Patterns | Array, Dynamic Programming, Divide and Conquer |
Google, Amazon, Meta, Microsoft, Goldman Sachs, Bloomberg, LinkedIn, DE Shaw, J.P. Morgan, Morgan Stanley, Adobe, Apple, Atlassian, Autodesk, Barclays, Cisco, Cognizant, HashedIn, Huawei, IBM, Infosys, Intel, and 1 more.
LeetCode #53 — Maximum Subarray
Given an integer array nums, find the subarray with the largest sum and return its sum.
Input: nums = [-2,1,-3,4,-1,2,1,-5,4] → Output: 6 (subarray [4,-1,2,1])
Input: nums = [1] → Output: 1
Input: nums = [5,4,-1,7,8] → Output: 23 (whole array)At each index i, you face a binary choice: extend the subarray ending at i-1 by including nums[i], or start a brand new subarray at i. The optimal choice is whichever gives the larger sum:
current_sum = max(nums[i], current_sum + nums[i])
If current_sum + nums[i] < nums[i], that means current_sum < 0 — a negative running sum only drags down the new element. So reset and start fresh. Track the maximum current_sum seen at any point.
If the running sum goes negative, throw it away and restart from the current element — a negative prefix never helps maximize a subarray sum.
Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
| i | nums[i] | current_sum | max_sum |
|---|---|---|---|
| 0 | -2 | -2 | -2 |
| 1 | 1 | 1 (reset) | 1 |
| 2 | -3 | -2 | 1 |
| 3 | 4 | 4 (reset) | 4 |
| 4 | -1 | 3 | 4 |
| 5 | 2 | 5 | 5 |
| 6 | 1 | 6 | 6 |
| 7 | -5 | 1 | 6 |
| 8 | 4 | 5 | 6 |
def maxSubArray(nums: list[int]) -> int:
current_sum = max_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sumclass Solution {
public int maxSubArray(int[] nums) {
int currentSum = nums[0], maxSum = nums[0];
for (int i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
}var maxSubArray = function(nums) {
let currentSum = nums[0], maxSum = nums[0];
for (let i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
};| Problem | Key Idea |
|---|---|
| LC #53 Maximum Subarray | Kadane's — reset when current_sum < 0 |
| LC #152 Maximum Product Subarray | Track both max and min (negatives flip sign) |
| LC #918 Maximum Circular Subarray | max(kadane, total_sum - min_subarray) |
| LC #560 Subarray Sum Equals K | Prefix sum + hash map |
| LC #209 Minimum Size Subarray Sum | Sliding window |
Tag on DSAPrep.dev under Dynamic Programming and Array.