Log inSign up
mediumLeetCodeNot Started

Maximum Subarray

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1 · Mixed Positive and Negative Numbers:

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: The contiguous subarray [4, -1, 2, 1] has the largest sum = 6.

Example 2 · Single Element Array:

Input: nums = [1]
Output: 1
Explanation: The only subarray is [1] with sum = 1.

Example 3 · All Negative Numbers:

Input: nums = [-5, -2, -8, -1, -4]
Output: -1
Explanation: The subarray [-1] has the largest sum = -1.

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Subarray definition (contiguous elements)
  • Running sum concepts
  • 1D Dynamic Programming state optimization

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the DP derivation behind Kadane's Algorithm.
  • Formulate optimal linear state transitions without auxiliary arrays.
  • Handle all-negative edge cases without false zero resets.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding maximum or minimum contiguous subarray sum.
  • Negative numbers make greedy expansion non-trivial.
  • Linear time constraint O(N) with O(1) space requirement.

Algorithmic Decision Tree:

  • When maximizing contiguous subarray sums: Use Kadane's algorithm to decide between continuing the current subarray or starting anew at each element.

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Nested Loops All Subarrays

Intuition

Check every subarray sum from starting index i to ending index j, tracking the maximum sum.

Algorithm

  1. 1. Initialize maxSum = nums[0].
  2. 2. For i from 0 to n-1: - currentSum = 0 - For j from i to n-1: - currentSum += nums[j] - maxSum = max(maxSum, currentSum).
  3. 3. Return maxSum.

Brute Force All Subarrays Exhaustive Enumeration

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [-2, 1, -3, 4, -1, 2, 1]
Current operationSTEP 1 OF 7
Subarray [0
Visual state
Values and pointers at this exact step
table
S
-2
1
-3
4
-1
2
1
0
↑ i=0, j=0
1
2
3
4
5
6
Subarray[-2]
Current Sum-2
Max Sum-2
Variables at this step
Subarray
[-2]
Current Sum
-2
Max Sum
-2
Check / comparison
Subarray [-2]: sum = -2.
Decision / next transition
Initialize maxSum = -2.
Why this step matters

Subarray [0..0]: First element is -2. Baseline maxSum is -2.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 int maxSubArray(vector<int>& nums) {
17 int n = nums.size();
18 int maxSum = nums[0];
19 for (int i = 0; i < n; ++i) {
20 int sum = 0;
21 for (int j = i; j < n; ++j) {
22 sum += nums[j];
23 maxSum = max(maxSum, sum);
24 }
25 }
26 return maxSum;
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
33 cout << "Maximum Subarray Sum: " << sol.maxSubArray(nums) << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N^2) — Evaluates all N*(N+1)/2 subarrays in nested loops, resulting in O(N2) time.
  • Space complexity: O(1) — Auxiliary memory is O(1).

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Divide and Conquer

Intuition

Split array in half; recursively find max subarray in left half, right half, or crossing the midpoint.

Algorithm

  1. 1. Base case: If left == right, return nums[left].
  2. 2. mid = (left + right) / 2.
  3. 3. Recursively find maxLeft = solve(left, mid) and maxRight = solve(mid + 1, right).
  4. 4. Compute maxCross: Expand from mid leftward to find max left sum, expand from mid+1 rightward to find max right sum, and sum them.
  5. 5. Return max(maxLeft, maxRight, maxCross).

Divide and Conquer Crossing Subarray Trace

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [-2, 1, -3, 4, -1, 2, 1]
Current operationSTEP 1 OF 7
Step 1 — Array Partition: Split at mid index 3
Visual state
Values and pointers at this exact step
table
S
-2
1
-3
4
-1
2
1
0
1
2
3
↑ Mid = 3 (val 4)
4
5
6
MidpointIndex 3
Left Half[-2, 1, -3]
Right Half[4, -1, 2, 1]
Variables at this step
Midpoint
Index 3
Left Half
[-2, 1, -3]
Right Half
[4, -1, 2, 1]
Check / comparison
Divide array at midpoint index 3: Left = [-2, 1, -3], Right = [4, -1, 2, 1].
Decision / next transition
Recursively solve left, right, and crossing subarrays.
Why this step matters

Step 1 — Array Partition: Split at mid index 3. Any maximal subarray lies completely in left, completely in right, or crosses the midpoint.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 int maxCrossingSum(vector<int>& nums, int left, int mid, int right) {
17 int leftSum = INT_MIN, sum = 0;
18 for (int i = mid; i >= left; --i) {
19 sum += nums[i];
20 leftSum = max(leftSum, sum);
21 }
22 int rightSum = INT_MIN;
23 sum = 0;
24 for (int i = mid + 1; i <= right; ++i) {
25 sum += nums[i];
26 rightSum = max(rightSum, sum);
27 }
28 return leftSum + rightSum;
29 }
30
31 int maxSubArrayHelper(vector<int>& nums, int left, int right) {
32 if (left == right) return nums[left];
33 int mid = left + (right - left) / 2;
34 int leftMax = maxSubArrayHelper(nums, left, mid);
35 int rightMax = maxSubArrayHelper(nums, mid + 1, right);
36 int crossMax = maxCrossingSum(nums, left, mid, right);
37 return max({leftMax, rightMax, crossMax});
38 }
39
40 int maxSubArray(vector<int>& nums) {
41 return maxSubArrayHelper(nums, 0, nums.size() - 1);
42 }
43};
44
45int main() {
46 Solution sol;
47 vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
48 cout << "Maximum Subarray Sum: " << sol.maxSubArray(nums) << endl;
49 return 0;
50}

Time & Space Complexity

  • Time complexity: O(N log N) — Recurrence is T(N) = 2T(N/2) + O(N), which by Master Theorem solves to O(N log N).
  • Space complexity: O(log N) — Recursion call stack depth is O(log N).

3. Kadane's Algorithm (Standard Linear DP)

Intuition

Iterate through the array, at each step deciding whether to add current element to running sum or start fresh.

Algorithm

  1. 1. Initialize currentSum = nums[0], maxSum = nums[0].
  2. 2. For i from 1 to n-1: - currentSum = max(nums[i], currentSum + nums[i]) - maxSum = max(maxSum, currentSum).
  3. 3. Return maxSum.

Kadane's Algorithm Running Maximum Subarray Trace

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [-2, 3, -1, 4, -2, 5]
Current operationSTEP 1 OF 7
Step 1 — Initialization at Index 0: Kadane's algorithm begins with the first element nums[0] = -2
Visual state
Values and pointers at this exact step
array
S
-2
3
-1
4
-2
5
0
↑ i = 0
1
2
3
4
5
Variables at this step
Current Index
0
Element Value
-2
Current Sum
-2
Max Sum
-2
Decision
Initial Seed
Check / comparison
First element: currentSum = -2, maxSum = -2.
Decision / next transition
Initialize running state with first element.
Why this step matters

Step 1 — Initialization at Index 0: Kadane's algorithm begins with the first element nums[0] = -2. Both local currentSum and global maxSum are initialized to -2.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 int maxSubArray(vector<int>& nums) {
17 int currentSum = nums[0];
18 int maxSum = nums[0];
19 for (size_t i = 1; i < nums.size(); ++i) {
20 currentSum = max(nums[i], currentSum + nums[i]);
21 maxSum = max(maxSum, currentSum);
22 }
23 return maxSum;
24 }
25};
26
27int main() {
28 Solution sol;
29 vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
30 cout << "Maximum Subarray Sum: " << sol.maxSubArray(nums) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N) — A single linear pass through N elements performing constant work per element.
  • Space complexity: O(1) — Only maintains two scalar variables. Space is strictly O(1).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Approach 1: Nested Loops All SubarraysO(N^2)O(1)Check every subarray sum from starting index i to ending index j, tracking the maximum sum.Repeated redundant scans over the input.
2.Approach 2: Divide and ConquerO(N log N)O(log N)Split array in half; recursively find max subarray in left half, right half, or crossing the midpoint.Auxiliary memory allocation or sorting step.
3.Approach 3: Kadane's Algorithm (Standard Linear DP)OptimalO(N)O(1)Iterate through the array, at each step deciding whether to add current element to running sum or start fresh.None. Asymptotically optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • All Negative Numbers [-5, -2, -8, -1, -4] — Input: `, Expected: ` —
  • All Positive Numbers [1, 2, 3, 4, 5] — Input: `, Expected: ` —
  • Single Element Array [7] — Input: `, Expected: ` —

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Maximum Subarray?

2.Why is the brute force approach suboptimal for large inputs in Maximum Subarray?

3.Which data structure or technique enables the optimal solution for Maximum Subarray?

Back to DSA Sheet