53. Maximum Subarray - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

1. Problem Statement

Description:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Examples:

Example 1:
- 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 of 6.
Example 2:
- Input: nums = [1]
- Output: 1
- Explanation: Since there is only one element, the maximum subarray is [1] with sum 1.
Example 3:
- Input: nums = [5, 4, -1, 7, 8]
- Output: 23
- Explanation: The entire array forms the maximum subarray with sum 23.

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

Hints

Hint 1:
When iterating through the array, ask yourself at each index: “Should I add the current element to the existing subarray or start a new subarray from here?”
Hint 2:
Think about dynamic programming. Can you store information at each step that tells you the maximum sum ending at that index?

Approaches

Approach 1: Brute Force

Explanation

The brute force method involves checking every possible contiguous subarray and computing its sum. You then keep track of the maximum sum encountered.

Steps:

Loop through every possible starting index i in the array.
For each i, loop through every possible ending index j (where j >= i).
Compute the sum of the subarray nums[i:j+1].
Keep track of the maximum sum found.

Complexity Analysis

Time Complexity:
- Without optimization: O(n³) (if you sum elements each time)
- With precomputed prefix sums: O(n²)
Space Complexity: O(1) or O(n) if you store a prefix sum array.

Visual Example

For nums = [a, b, c]:

Subarrays: [a], [a, b], [a, b, c], [b], [b, c], [c]
Calculate each sum and determine the maximum.

Python Code

Python3

. . . .

Java Code

Java

. . . .

Approach 2: Optimal Solution Using Kadane’s Algorithm

Explanation

Kadane’s Algorithm uses dynamic programming to solve the problem in O(n) time. The idea is to iterate through the array while keeping track of the maximum subarray sum ending at the current position and updating a global maximum if necessary.

Steps:

Initialization:
- Let current_max and global_max be the first element of the array.
Iteration:
- For each element nums[i] from index 1 onward:
  - Update current_max as the maximum between nums[i] (starting a new subarray) and current_max + nums[i] (extending the current subarray).
  - Update global_max to be the maximum of itself and current_max.
Result:
- Return global_max as it represents the largest sum found.

Complexity Analysis

Time Complexity: O(n) – each element is processed once.
Space Complexity: O(1) – only constant extra space is used.

Visual Example Walkthrough

For nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

Index	Element	Current Max Calculation	current_max	global_max
0	-2	Initialization	-2	-2
1	1	max(1, -2 + 1) = max(1, -1)	1	max(-2, 1)=1
2	-3	max(-3, 1 + (-3)) = max(-3, -2)	-2	1
3	4	max(4, -2 + 4) = max(4, 2)	4	max(1, 4)=4
4	-1	max(-1, 4 + (-1)) = max(-1, 3)	3	4
5	2	max(2, 3 + 2) = max(2, 5)	5	max(4, 5)=5
6	1	max(1, 5 + 1) = max(1, 6)	6	max(5, 6)=6
7	-5	max(-5, 6 + (-5)) = max(-5, 1)	1	6
8	4	max(4, 1 + 4) = max(4, 5)	5	max(6, 5)=6

The final answer is 6.

Python Code

Python3

. . . .

Java Code

Java

. . . .

Common Mistakes

Initialization Errors:
Failing to initialize current_max and global_max with the first element can lead to wrong answers, especially when all numbers are negative.
Not Handling Negative Numbers:
Some may assume that the maximum subarray must have a positive sum. However, if all numbers are negative, the maximum subarray is the largest (least negative) element.
Overcomplicating the Problem:
Using unnecessarily complex methods (like brute force without optimizations) can lead to timeouts for large inputs.

Edge Cases

Single Element Array:
The algorithm should return that element.
All Negative Numbers:
Ensure that your solution correctly identifies the maximum element when no positive sum exists.
Large Arrays:
The optimal solution (Kadane’s algorithm) is necessary when nums.length is large (up to 10^5).

Alternative Variations of the Problem

Maximum Product Subarray:
Instead of summing, you need to find the contiguous subarray with the largest product.
Circular Maximum Subarray:
The array is considered circular, meaning that the subarray can wrap from the end of the array back to the beginning.

Best Time to Buy and Sell Stock:
Find the maximum profit by choosing the best day to buy and sell.
Longest Increasing Subsequence:
Identify the longest subsequence of a given sequence in which the elements are in sorted order.
Subarray Sum Equals K:
Count the number of contiguous subarrays that sum to a given value.
Maximum Product Subarray:
Find the contiguous subarray within an array (containing at least one number) which has the largest product.

53. Maximum Subarray - Detailed Explanation

1. Problem Statement

Hints

Approaches

Approach 1: Brute Force

Explanation

Complexity Analysis

Visual Example

Python Code

Java Code

Approach 2: Optimal Solution Using Kadane’s Algorithm

Explanation

Complexity Analysis

Visual Example Walkthrough

Python Code

Java Code

Common Mistakes

Edge Cases

Alternative Variations of the Problem

Related Problems for Further Practice