Maximum Subarray (LeetCode
Learn how to solve the Maximum Subarray problem using brute force, prefix sums, and the optimal Kadane’s Algorithm. Includes intuition, dry runs, Java code, complexity analysis, edge cases, interview tips, and production applications.
Introduction
Maximum Subarray is one of the most frequently asked array and dynamic programming interview problems.
It is commonly associated with companies such as:
- Amazon
- Microsoft
- Meta
- Apple
- Adobe
- Bloomberg
- Goldman Sachs
- JPMorgan Chase
This problem tests your understanding of:
- Contiguous subarrays
- Running sums
- Brute-force optimization
- Prefix sums
- Greedy decision-making
- Dynamic programming
- Kadane’s Algorithm
- Time and space complexity
The most important insight is:
At every index, decide whether to extend the previous subarray or start a new subarray from the current element.
Problem Statement
Given an integer array nums, find the contiguous subarray with the largest sum and return that sum.
A subarray must contain at least one element.
Example 1
Input
nums = [-2,1,-3,4,-1,2,1,-5,4]
Output
6
Explanation:
Maximum Subarray
[4,-1,2,1]
Sum
4 + (-1) + 2 + 1 = 6
Example 2
Input
nums = [1]
Output
1
The only available subarray is:
[1]
Example 3
Input
nums = [5,4,-1,7,8]
Output
23
Explanation:
5 + 4 - 1 + 7 + 8 = 23
The entire array is the maximum-sum subarray.
What Is a Subarray?
A subarray is a contiguous section of an array.
For:
[1,2,3]
Valid subarrays include:
[1]
[2]
[3]
[1,2]
[2,3]
[1,2,3]
This is not a valid subarray:
[1,3]
because the elements are not contiguous.
Subarray vs Subsequence
| Subarray | Subsequence |
|---|---|
| Must be contiguous | Does not need to be contiguous |
| Preserves order | Preserves order |
[2,3] from [1,2,3] |
[1,3] from [1,2,3] |
| Usually processed with windows or DP | Often processed with DP or recursion |
The Maximum Subarray problem requires a contiguous range.
Approach 1 — Brute Force with Three Loops
Idea
Generate every possible subarray.
For each subarray:
- Choose a starting index.
- Choose an ending index.
- Calculate the sum of elements between them.
- Update the maximum sum.
Brute Force Flow
graph TD
Choose_Start["Choose Start"] --> Choose_End["Choose End"]
Choose_End["Choose End"] --> Calculate_Subarray_Sum["Calculate Subarray Sum"]
Calculate_Subarray_Sum["Calculate Subarray Sum"] --> Update_Maximum["Update Maximum"]
Java Code — Three Loops
public class MaximumSubarrayBruteForce {
public int maxSubArray(int[] nums) {
int maximumSum = Integer.MIN_VALUE;
for (int start = 0;
start < nums.length;
start++) {
for (int end = start;
end < nums.length;
end++) {
int currentSum = 0;
for (int index = start;
index <= end;
index++) {
currentSum += nums[index];
}
maximumSum = Math.max(
maximumSum,
currentSum);
}
}
return maximumSum;
}
}
Complexity
| Complexity | Value |
|---|---|
| Time | O(n³) |
| Space | O(1) |
This approach repeatedly calculates the same sums and is too slow for large arrays.
Approach 2 — Improved Brute Force
Core Idea
Instead of recalculating every subarray sum from the beginning, maintain a running sum for each starting index.
For every start:
currentSum = 0
Then extend the ending index one element at a time.
Example
For:
[1,2,3]
Starting at index 0:
[1] → Sum = 1
[1,2] → Sum = 3
[1,2,3] → Sum = 6
We add only the newly included element.
Java Code — Improved Brute Force
public class MaximumSubarrayQuadratic {
public int maxSubArray(int[] nums) {
int maximumSum = Integer.MIN_VALUE;
for (int start = 0;
start < nums.length;
start++) {
int currentSum = 0;
for (int end = start;
end < nums.length;
end++) {
currentSum += nums[end];
maximumSum = Math.max(
maximumSum,
currentSum);
}
}
return maximumSum;
}
}
Complexity
| Complexity | Value |
|---|---|
| Time | O(n²) |
| Space | O(1) |
This is better than the three-loop solution but still inefficient for very large arrays.
Approach 3 — Prefix Sum
Core Idea
A prefix sum array allows the sum of any subarray to be calculated quickly.
Define:
prefix[i]
as the sum of the first i elements.
For:
nums = [2,-1,3,4]
Prefix sums:
prefix = [0,2,1,4,8]
The sum from index left to right is:
prefix[right + 1] - prefix[left]
Example
To calculate the sum of:
nums[1..3]
which is:
[-1,3,4]
Use:
prefix[4] - prefix[1]
=
8 - 2
=
6
Java Code — Prefix Sum
public class MaximumSubarrayUsingPrefixSum {
public int maxSubArray(int[] nums) {
int[] prefix =
new int[nums.length + 1];
for (int i = 0;
i < nums.length;
i++) {
prefix[i + 1] =
prefix[i] + nums[i];
}
int maximumSum = Integer.MIN_VALUE;
for (int start = 0;
start < nums.length;
start++) {
for (int end = start;
end < nums.length;
end++) {
int currentSum =
prefix[end + 1]
- prefix[start];
maximumSum = Math.max(
maximumSum,
currentSum);
}
}
return maximumSum;
}
}
Complexity
| Complexity | Value |
|---|---|
| Time | O(n²) |
| Space | O(n) |
Prefix sums make each range-sum calculation constant time, but all possible subarrays are still checked.
Approach 4 — Kadane’s Algorithm
Core Idea
At every element, make one decision:
Should I extend the existing subarray?
or
Should I start a new subarray here?
For the current number:
currentSum =
max(
currentNumber,
currentSum + currentNumber
)
Then update:
maximumSum =
max(
maximumSum,
currentSum
)
Why Restart the Subarray?
Suppose the running sum becomes negative.
Example:
Running Sum = -5
Current Number = 4
Options:
Extend Previous Subarray
-5 + 4 = -1
or:
Start New Subarray
4
Starting again at 4 gives a better result.
A negative prefix can never improve the sum of a future subarray.
Kadane’s Algorithm Flow
graph TD
Read_Current_Number["Read Current Number"] --> Extend_Previous_Sum["Extend Previous Sum"]
Extend_Previous_Sum["Extend Previous Sum"] --> or["or"]
or["or"] --> Start_New_Subarray["Start New Subarray"]
Start_New_Subarray["Start New Subarray"] --> Update_Current_Sum["Update Current Sum"]
Update_Current_Sum["Update Current Sum"] --> Update_Global_Maximum["Update Global Maximum"]
Dry Run
Input:
[-2,1,-3,4,-1,2,1,-5,4]
Initialize:
currentSum = -2
maximumSum = -2
Index 1
Current value:
1
Options:
Start New
1
Extend Existing
-2 + 1 = -1
Choose:
currentSum = 1
Update:
maximumSum = 1
Index 2
Current value:
-3
Options:
Start New
-3
Extend Existing
1 + (-3) = -2
Choose:
currentSum = -2
Maximum remains:
1
Index 3
Current value:
4
Options:
Start New
4
Extend Existing
-2 + 4 = 2
Choose:
currentSum = 4
Update:
maximumSum = 4
Index 4
Current value:
-1
currentSum =
max(-1, 4 - 1)
=
3
Maximum remains:
4
Index 5
Current value:
2
currentSum =
max(2, 3 + 2)
=
5
Update:
maximumSum = 5
Index 6
Current value:
1
currentSum =
max(1, 5 + 1)
=
6
Update:
maximumSum = 6
Index 7
Current value:
-5
currentSum =
max(-5, 6 - 5)
=
1
Maximum remains:
6
Index 8
Current value:
4
currentSum =
max(4, 1 + 4)
=
5
Maximum remains:
6
Final answer:
6
Dry Run Table
| Index | Value | Extend Previous | Start New | Current Sum | Maximum Sum |
|---|---|---|---|---|---|
| 0 | -2 | — | -2 | -2 | -2 |
| 1 | 1 | -1 | 1 | 1 | 1 |
| 2 | -3 | -2 | -3 | -2 | 1 |
| 3 | 4 | 2 | 4 | 4 | 4 |
| 4 | -1 | 3 | -1 | 3 | 4 |
| 5 | 2 | 5 | 2 | 5 | 5 |
| 6 | 1 | 6 | 1 | 6 | 6 |
| 7 | -5 | 1 | -5 | 1 | 6 |
| 8 | 4 | 5 | 4 | 5 | 6 |
Java Code — Kadane’s Algorithm
public class MaximumSubarray {
public int maxSubArray(int[] nums) {
int currentSum = nums[0];
int maximumSum = nums[0];
for (int i = 1;
i < nums.length;
i++) {
currentSum = Math.max(
nums[i],
currentSum + nums[i]);
maximumSum = Math.max(
maximumSum,
currentSum);
}
return maximumSum;
}
}
Alternative Kadane Implementation
public class Solution {
public int maxSubArray(int[] nums) {
int currentSum = 0;
int maximumSum = Integer.MIN_VALUE;
for (int number : nums) {
currentSum += number;
maximumSum = Math.max(
maximumSum,
currentSum);
if (currentSum < 0) {
currentSum = 0;
}
}
return maximumSum;
}
}
This version resets the running sum whenever it becomes negative.
The maximum must be updated before resetting so that arrays containing only negative values are handled correctly.
Complexity Analysis
| Complexity | Value |
|---|---|
| Time | O(n) |
| Space | O(1) |
Kadane’s Algorithm processes each element exactly once.
No additional arrays or collections are needed.
Dynamic Programming Interpretation
Kadane’s Algorithm can be understood as a space-optimized dynamic programming solution.
Define:
dp[i]
as the maximum subarray sum ending exactly at index i.
Then:
dp[i]
=
max(
nums[i],
dp[i - 1] + nums[i]
)
The answer is:
maximum value in dp
DP Array Version
public class MaximumSubarrayUsingDP {
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int maximumSum = dp[0];
for (int i = 1;
i < nums.length;
i++) {
dp[i] = Math.max(
nums[i],
dp[i - 1] + nums[i]);
maximumSum = Math.max(
maximumSum,
dp[i]);
}
return maximumSum;
}
}
DP Complexity
| Complexity | Value |
|---|---|
| Time | O(n) |
| Space | O(n) |
Kadane’s Algorithm optimizes this to constant space because only the previous state is needed.
How to Return the Actual Subarray
The standard problem asks only for the maximum sum.
A common follow-up asks for the start and end indices of the maximum subarray.
Maintain:
- Current start index
- Best start index
- Best end index
Java Code — Return Maximum Subarray Range
public class MaximumSubarrayRange {
public SubarrayResult findMaximumSubarray(
int[] nums) {
int currentSum = nums[0];
int maximumSum = nums[0];
int currentStart = 0;
int bestStart = 0;
int bestEnd = 0;
for (int i = 1;
i < nums.length;
i++) {
if (nums[i] > currentSum + nums[i]) {
currentSum = nums[i];
currentStart = i;
} else {
currentSum += nums[i];
}
if (currentSum > maximumSum) {
maximumSum = currentSum;
bestStart = currentStart;
bestEnd = i;
}
}
return new SubarrayResult(
maximumSum,
bestStart,
bestEnd);
}
public record SubarrayResult(
int maximumSum,
int startIndex,
int endIndex) {
}
}
Example Result
Input:
[-2,1,-3,4,-1,2,1,-5,4]
Result:
Maximum Sum = 6
Start Index = 3
End Index = 6
Subarray = [4,-1,2,1]
Return the Actual Values
import java.util.Arrays;
public class MaximumSubarrayValues {
public int[] findMaximumSubarray(
int[] nums) {
int currentSum = nums[0];
int maximumSum = nums[0];
int currentStart = 0;
int bestStart = 0;
int bestEnd = 0;
for (int i = 1;
i < nums.length;
i++) {
if (nums[i] > currentSum + nums[i]) {
currentSum = nums[i];
currentStart = i;
} else {
currentSum += nums[i];
}
if (currentSum > maximumSum) {
maximumSum = currentSum;
bestStart = currentStart;
bestEnd = i;
}
}
return Arrays.copyOfRange(
nums,
bestStart,
bestEnd + 1);
}
}
Edge Cases
Single Element
Input
[5]
Output
5
All Positive Numbers
Input
[1,2,3,4]
Output
10
The entire array is selected.
All Negative Numbers
Input
[-8,-3,-6,-2,-5,-4]
Output
-2
The maximum subarray contains the largest individual element.
This is why initializing the answer to 0 is incorrect.
Mixed Positive and Negative Values
Input
[5,-2,3,4]
Output
10
Maximum subarray:
[5,-2,3,4]
Zeroes
Input
[-2,0,-1]
Output
0
The maximum subarray is:
[0]
Large Negative Prefix
Input
[-100,5,6]
Output
11
The negative prefix is discarded.
Why Initialize with the First Element?
Incorrect initialization:
int maximumSum = 0;
fails for:
[-5,-2,-8]
It would incorrectly return:
0
But an empty subarray is not allowed.
The correct result is:
-2
Therefore, initialize with:
int currentSum = nums[0];
int maximumSum = nums[0];
Integer Overflow Consideration
In production systems, the sum may exceed the int range.
Use long when input constraints are large.
public class MaximumSubarrayLong {
public long maxSubArray(long[] nums) {
long currentSum = nums[0];
long maximumSum = nums[0];
for (int i = 1;
i < nums.length;
i++) {
currentSum = Math.max(
nums[i],
currentSum + nums[i]);
maximumSum = Math.max(
maximumSum,
currentSum);
}
return maximumSum;
}
}
Comparison of Approaches
| Approach | Time | Space | Recommended |
|---|---|---|---|
| Three nested loops | O(n³) | O(1) | No |
| Running sum brute force | O(n²) | O(1) | Good starting point |
| Prefix sum | O(n²) | O(n) | Useful concept |
| DP array | O(n) | O(n) | Good explanation |
| Kadane’s Algorithm | O(n) | O(1) | Best |
Common Interview Mistakes
Mistake 1 — Allowing an Empty Subarray
The problem requires at least one element.
Returning 0 for an all-negative array is incorrect.
Mistake 2 — Resetting Before Updating the Maximum
Incorrect:
currentSum += number;
if (currentSum < 0) {
currentSum = 0;
}
maximumSum = Math.max(
maximumSum,
currentSum);
This can lose the correct result for negative arrays.
Update the maximum before resetting, or use the standard recurrence.
Mistake 3 — Confusing Subarray with Subsequence
The selected elements must be contiguous.
Mistake 4 — Returning the Maximum Element Only
The best result may contain multiple elements.
Example:
[4,-1,2,1]
has a sum of:
6
which is greater than any individual element.
Mistake 5 — Forgetting the First Element
Starting iteration at index 1 requires initialization from index 0.
Mistake 6 — Not Explaining Why Negative Prefixes Are Discarded
A negative running sum reduces every future sum.
Therefore, it is always better to start fresh after a negative prefix.
Production Applications
The Maximum Subarray pattern appears in:
- Stock profit-and-loss streak analysis
- Revenue growth periods
- Customer engagement analysis
- Network traffic monitoring
- Sensor signal processing
- Resource utilization analysis
- Financial portfolio performance
- Fraud-score trend detection
- Sales performance windows
- Time-series anomaly analysis
Real-World Example — Daily Profit and Loss
Suppose a business records daily profit and loss:
[-20,10,-5,30,-10,15,-40,20]
The maximum profitable continuous period is:
[10,-5,30,-10,15]
Sum:
40
Kadane’s Algorithm identifies the best continuous business period in linear time.
Real-World Example — Network Traffic Gain
Suppose changes in useful network throughput are:
[-3,5,2,-6,8,4,-2]
The maximum positive continuous segment is:
[8,4]
or possibly a longer range depending on the accumulated sum.
The same running-sum decision identifies the strongest sustained period.
Follow-Up Question 1 — Return the Subarray
Track start and end indices while running Kadane’s Algorithm.
Time remains:
O(n)
Space remains:
O(1)
excluding the returned values.
Follow-Up Question 2 — Maximum Circular Subarray
This becomes LeetCode #918.
The answer is either:
- A normal maximum subarray, or
- A circular subarray formed by excluding the minimum subarray.
Formula:
Circular Maximum
=
Total Sum - Minimum Subarray Sum
Special handling is required when every value is negative.
Follow-Up Question 3 — Maximum Product Subarray
This becomes LeetCode #152.
Because negative numbers can turn minimum products into maximum products, track:
- Maximum product ending here
- Minimum product ending here
Follow-Up Question 4 — Maximum Sum with One Deletion
Use dynamic programming with two states:
- Maximum sum ending here without deletion
- Maximum sum ending here after one deletion
Follow-Up Question 5 — Maximum Subarray of Fixed Size
Use the Sliding Window technique.
For a fixed window size k:
Time: O(n)
Space: O(1)
Follow-Up Question 6 — What If the Array Is Streaming?
Kadane’s Algorithm works well with streaming input.
Maintain only:
- Current maximum ending here
- Global maximum
No complete array is required when only the maximum sum is needed.
Follow-Up Question 7 — Can Divide and Conquer Be Used?
Yes.
Divide the array into two halves.
The maximum subarray is one of:
- Entirely in the left half
- Entirely in the right half
- Crossing the middle
Typical complexity:
O(n log n)
Kadane’s Algorithm remains better at:
O(n)
Interview Explanation
A strong interview explanation could be:
I define the current sum as the maximum subarray sum ending at the current index. For each value, I decide whether to extend the previous subarray or start a new subarray at the current value. If the previous running sum hurts the result, I discard it. I also track the best sum seen globally. This is Kadane’s Algorithm and runs in O(n) time with O(1) extra space.
Interview Tips
Interviewers commonly ask:
- What is the difference between a subarray and a subsequence?
- Why does Kadane’s Algorithm work?
- Why can a negative prefix be discarded?
- How do you handle all-negative arrays?
- How do you return the actual subarray?
- What is the dynamic programming recurrence?
- Can this work with streaming data?
- How would you solve the circular version?
- How does the solution change for a fixed-size window?
- Can divide and conquer solve the problem?
Explain the decision to extend or restart before writing code.
Unit Tests
import static org.junit.jupiter.api.Assertions.assertEquals;
import org.junit.jupiter.api.Test;
class MaximumSubarrayTest {
private final MaximumSubarray solution =
new MaximumSubarray();
@Test
void shouldFindMaximumSubarrayInMixedArray() {
int[] nums =
{-2, 1, -3, 4, -1, 2, 1, -5, 4};
assertEquals(
6,
solution.maxSubArray(nums));
}
@Test
void shouldHandleSingleElement() {
int[] nums = {1};
assertEquals(
1,
solution.maxSubArray(nums));
}
@Test
void shouldHandleAllPositiveValues() {
int[] nums = {5, 4, -1, 7, 8};
assertEquals(
23,
solution.maxSubArray(nums));
}
@Test
void shouldHandleAllNegativeValues() {
int[] nums = {-8, -3, -6, -2, -5, -4};
assertEquals(
-2,
solution.maxSubArray(nums));
}
@Test
void shouldHandleZero() {
int[] nums = {-2, 0, -1};
assertEquals(
0,
solution.maxSubArray(nums));
}
}
Summary
The Maximum Subarray problem demonstrates how repeated range calculations can be replaced with a simple dynamic programming decision.
At every index, decide whether to:
- Extend the previous subarray, or
- Start a new subarray at the current element
Kadane’s Algorithm achieves the optimal complexity:
Time: O(n)
Space: O(1)
It correctly handles positive values, negative values, zeroes, and all-negative arrays.
Key Takeaways
- A subarray must be contiguous.
- Brute force checks every possible range.
- Running sums reduce O(n³) to O(n²).
- Prefix sums calculate range sums efficiently.
- Kadane’s Algorithm uses dynamic programming.
- Track the maximum subarray ending at each index.
- Decide whether to extend or restart.
- Discard negative prefixes because they hurt future sums.
- Initialize using the first element.
- Handle all-negative arrays correctly.
- Achieve O(n) time and O(1) extra space.
- Track indices when the actual subarray is required.
- Connect the pattern to time-series and financial analysis.