Interview preparation
Maximum Subarray (Kadane's Algorithm)
MediumArraysDynamic Programming
AmazonMicrosoftAppleGoldman Sachs Community-reported practice tags — not verified company questions.
1Problem statement
Given an integer array nums, find the contiguous subarray (containing at least one number) with the largest sum and return that sum.
2Examples
Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: The subarray [4, -1, 2, 1] has the largest sum 6.
Input: nums = [1]
Output: 1
Input: nums = [5, 4, -1, 7, 8]
Output: 23
3Constraints
- 1 ≤ nums.length ≤ 10⁵
- −10⁴ ≤ nums[i] ≤ 10⁴
4Approaches
Approach 1
Brute Force
Try every start and end index and sum each subarray.
Time O(n³) (O(n²) with running sums)Space O(1)
Approach 2
Better: Divide and Conquer
Best subarray is in the left half, the right half, or crosses the middle.
Time O(n log n)Space O(log n)
Approach 3
Optimal: Kadane's Algorithm
best ending here = max(num, best ending at previous + num). Track the overall maximum.
Time O(n)Space O(1)
5Code (optimal approach)
Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.
function maxSubArray(nums) {
let current = nums[0];
let best = nums[0];
for (let i = 1; i < nums.length; i++) {
current = Math.max(nums[i], current + nums[i]);
best = Math.max(best, current);
}
return best;
}
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
console.log(maxSubArray([1]));
console.log(maxSubArray([5, 4, -1, 7, 8]));
6Complexity
Time
O(n)
Space
O(1)
7Visual walkthrough
- 1.current = -2, best = -2
- 2.num 1: current = max(1, -2 + 1) = 1, best = 1
- 3.num -3: current = max(-3, 1 - 3) = -2
- 4.num 4: current = max(4, -2 + 4) = 4, best = 4
- 5.num -1, 2, 1: current = 3, 5, 6 → best = 6
- 6.num -5, 4: current = 1, 5 → best stays 6