Loading…
Maximum Subarray is a easy coding interview question covering arrays, dynamic programming — the kind asked at FAANG (Facebook/Meta, Apple, Amazon, Netflix, Google) and AI-first companies like Anthropic, OpenAI, and Nvidia.
Given an integer array nums, find the contiguous subarray with the largest sum and return its sum.
Example: [-2,1,-3,4,-1,2,1,-5,4] -> 6 (subarray [4,-1,2,1])
This problem has an O(n) solution using Kadane's algorithm.
Try it yourself first
In an interview you'd get about 15 minutes for a easy question. Sketch an approach before peeking — struggling is where the learning happens.
Stuck? Reveal them one at a time — each hint gives away a little more.
Ready to compare notes? The full solution, visualization, and complexity analysis are below.
Kadane's algorithm finds the maximum-sum contiguous subarray in O(n) by tracking the best sum ending at each position. At each element, you either extend the previous subarray or start fresh — whichever is larger.
| ▶ | def max_subarray(nums: list[int]) -> int: |
| ▶ | current_sum = max_sum = nums[0] |
| 3 | for num in nums[1:]: |
| 4 | current_sum = max(num, current_sum + num) |
| 5 | max_sum = max(max_sum, current_sum) |
| 6 | return max_sum |
| 7 | |
| 8 | def max_subarray_with_indices(nums): |
| 9 | best_start = best_end = 0 |
| 10 | current_start = 0 |
| 11 | current_sum = max_sum = nums[0] |
| 12 | for i, num in enumerate(nums[1:], 1): |
| 13 | if current_sum + num < num: |
| 14 | current_sum = num |
| 15 | current_start = i |
| 16 | else: |
| 17 | current_sum += num |
| 18 | if current_sum > max_sum: |
| 19 | max_sum = current_sum |
| 20 | best_start, best_end = current_start, i |
| 21 | return max_sum, nums[best_start:best_end+1] |
Start: current_sum = max_sum = nums[0] = -2.
Key Insights
A full interview loop is more than one round. These are the others, each with what is on the site for it.