Maximum Subarray solution and explanation
TCS
Infosys
9 more videos on this problem
Maximum Subarray - Amazon Coding Interview Question - Leetcode 53 - PythonNeetCode · 8:03 · 745K views
Maximum Sub-Array Sum (LeetCode 53) | Kadane's Algorithm | Study AlgorithmsNikhil Lohia · 9:03 · 73K views
Maximum Subarray (Kadane's Algorithm) - Leetcode 53 - Dynamic Programming (Python)Greg Hogg · 4:40 · 42K views
Maximum Subarray | Kadane's Algorithm | Leetcode 53Technosage · 7:20 · 29K views
Maximum Subarray (Leetcode #53 SOLVED)Byte by Byte · 17:24 · 15K views
LeetCode 53 | Maximum Subarray Solution (Kadane's Algorithm) Visually Explained | Top Interview 150ByteQuest · 6:01 · 9K views
Maximum Subarray - LeetCode 53 - Coding Interview QuestionsOne Code Man · 6:28 · 5K views
Maximum Subarray - LeetCode 53 - JavaScriptAlgoJS · 4:43 · 5K views
LeetCode 53: Maximum Subarray | Dynamic ProgrammingAbstracted Away · 7:46 · 4K views
Maximum Subarray - LeetCode 53 - Java | Kadane's AlgorithmLeetCode University · 18:21 · 2K views
The problem
Given an integer array nums, find the subarray with the largest sum, and return its sum.
Example 1:
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.
Example 2:
Input: nums = [1] Output: 1 Explanation: The subarray [1] has the largest sum 1.
Example 3:
Input: nums = [5,4,-1,7,8] Output: 23 Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 104
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Approach overview
Problem Overview: Given an integer array nums, find the contiguous subarray with the largest possible sum and return that sum. The challenge is identifying the best subarray without checking every possible range.
Approach 1: Kadane's Algorithm (O(n) time, O(1) space)
Kadane's Algorithm scans the array once while maintaining the maximum sum ending at the current position. At each index, you decide whether to extend the previous subarray (current_sum + nums[i]) or start a new subarray at the current element. This works because any negative running sum only hurts future results, so resetting when the sum becomes smaller than the current element keeps the best candidate alive. You track a global maximum while iterating. The algorithm uses only two variables and runs in linear time, making it the most efficient and commonly expected solution for this problem.
The idea closely relates to dynamic programming. Each state represents the best subarray ending at index i, computed from the state at i-1. Because the recurrence depends only on the previous value, the DP table compresses into constant space.
Approach 2: Divide and Conquer (O(n log n) time, O(log n) space)
The divide and conquer strategy splits the array into two halves recursively. For each segment, compute three values: the best subarray entirely in the left half, the best entirely in the right half, and the best crossing the midpoint. The crossing sum is calculated by expanding from the midpoint outward to capture the maximum suffix of the left side and maximum prefix of the right side. The final answer for that segment is the maximum of these three candidates.
This method demonstrates how the problem can be broken into independent subproblems, a common pattern in divide and conquer algorithms. Although slower than Kadane's algorithm due to recursive splitting and merging, it helps build intuition about how subarray boundaries interact across partitions. The recursion depth contributes O(log n) auxiliary space.
Both approaches operate on a simple array structure and rely on tracking partial sums rather than enumerating all subarrays.
Recommended for interviews: Kadane's Algorithm is the expected answer. Interviewers want to see that you recognize the linear-time dynamic programming pattern and can derive the recurrence max(nums[i], current_sum + nums[i]). Mentioning the divide and conquer solution shows deeper understanding of the problem structure, but implementing Kadane's algorithm cleanly demonstrates strong algorithmic intuition and optimal complexity.
Approach 1: Approach 1: Kadane's Algorithm
This approach uses Kadane's Algorithm, which is an efficient way to find the maximum subarray sum in linear time.
We iterate through the array, keeping track of the maximum sum of the subarray ending at the current position and the overall maximum sum found so far.
The algorithm maintains two variables: current_max, which is the maximum sum of the subarray that ends at the current index, and global_max, which is the maximum sum found so far.
def max_sub_array(nums):
current_max = nums[0]
global_max = nums[0]
for i in range(1, len(nums)):
current_max = max(nums[i], current_max + nums[i])
if current_max > global_max:
global_max = current_max
return global_max
# Example usage
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Maximum subarray sum is", max_sub_array(nums))public class MaxSubArray {
public int maxSubArray(int[] nums) {
int currentMax = nums[0];
int globalMax = nums[0];
for (int i = 1; i < nums.length; i++) {
currentMax = Math.max(nums[i], currentMax + nums[i]);
if (currentMax > globalMax) {
globalMax = currentMax;
}
}
return globalMax;
}
public static void main(String[] args) {
MaxSubArray solution = new MaxSubArray();
int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println("Maximum subarray sum is " + solution.maxSubArray(nums));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxSubArray(vector<int>& nums) {
int current_max = nums[0];
int global_max = nums[0];
for (size_t i = 1; i < nums.size(); i++) {
current_max = max(nums[i], current_max + nums[i]);
global_max = max(global_max, current_max);
}
return global_max;
}
int main() {
vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
cout << "Maximum subarray sum is " << maxSubArray(nums) << endl;
return 0;
}function maxSubArray(nums) {
let currentMax = nums[0];
let globalMax = nums[0];
for (let i = 1; i < nums.length; i++) {
currentMax = Math.max(nums[i], currentMax + nums[i]);
if (currentMax > globalMax) {
globalMax = currentMax;
}
}
return globalMax;
}
// Example usage
const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log("Maximum subarray sum is", maxSubArray(nums));#include <stdio.h>
#include <limits.h>
int maxSubArray(int* nums, int numsSize) {
int current_max = nums[0];
int global_max = nums[0];
for (int i = 1; i < numsSize; i++) {
if (current_max < 0) {
current_max = nums[i];
} else {
current_max += nums[i];
}
if (current_max > global_max) {
global_max = current_max;
}
}
return global_max;
}
int main() {
int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int size = sizeof(nums)/sizeof(nums[0]);
int max_sum = maxSubArray(nums, size);
printf("Maximum subarray sum is %d\n", max_sum);
return 0;
}using System;
public class MaxSubArray {
public int MaxSubArraySum(int[] nums) {
int currentMax = nums[0];
int globalMax = nums[0];
for (int i = 1; i < nums.Length; i++) {
currentMax = Math.Max(nums[i], currentMax + nums[i]);
if (currentMax > globalMax) {
globalMax = currentMax;
}
}
return globalMax;
}
public static void Main(string[] args) {
MaxSubArray solution = new MaxSubArray();
int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
Console.WriteLine("Maximum subarray sum is " + solution.MaxSubArraySum(nums));
}
}This Python code follows Kadane's Algorithm, using simple variable assignments and max function calls to calculate the maximum subarray sum.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Approach 2: Divide and Conquer
This approach splits the array into two halves and finds the maximum subarray sum for each half recursively. It also considers the possibility of the maximum subarray crossing the midpoint.
To find the maximum crossing subarray, we begin at the midpoint and expand outward to the left and right, keeping track of the maximum sum.
This approach effectively divides the problem into smaller subproblems and conquers each independently, then combines their results.
def max_crossing_sum(arr, left, mid, right):
left_sum = float('-inf')
total = 0
for i in range(mid, left - 1, -1):
total += arr[i]
if total > left_sum:
left_sum = total
right_sum = float('-inf')
total = 0
for i in range(mid + 1, right + 1):
total += arr[i]
if total > right_sum:
right_sum = total
return left_sum + right_sum
def max_sub_array_sum(arr, left, right):
if left == right:
return arr[left]
mid = (left + right) // 2
left_max = max_sub_array_sum(arr, left, mid)
right_max = max_sub_array_sum(arr, mid + 1, right)
crossing_max = max_crossing_sum(arr, left, mid, right)
return max(left_max, right_max, crossing_max)
# Example usage
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Maximum subarray sum is", max_sub_array_sum(nums, 0, len(nums) - 1))public class MaxSubArrayDivideConquer {
public int maxCrossingSum(int[] arr, int l, int m, int h) {
int sum = 0;
int left_sum = Integer.MIN_VALUE;
for (int i = m; i >= l; i--) {
sum += arr[i];
if (sum > left_sum)
left_sum = sum;
}
sum = 0;
int right_sum = Integer.MIN_VALUE;
for (int i = m + 1; i <= h; i++) {
sum += arr[i];
if (sum > right_sum)
right_sum = sum;
}
return left_sum + right_sum;
}
public int maxSubArraySum(int[] arr, int l, int h) {
if (l == h)
return arr[l];
int m = (l + h) / 2;
int left_max = maxSubArraySum(arr, l, m);
int right_max = maxSubArraySum(arr, m + 1, h);
int cross_max = maxCrossingSum(arr, l, m, h);
return Math.max(Math.max(left_max, right_max), cross_max);
}
public static void main(String[] args) {
MaxSubArrayDivideConquer solution = new MaxSubArrayDivideConquer();
int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println("Maximum subarray sum is " + solution.maxSubArraySum(nums, 0, nums.length - 1));
}
}#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int maxCrossingSum(vector<int>& nums, int l, int m, int h) {
int sum = 0;
int left_sum = INT_MIN;
for (int i = m; i >= l; i--) {
sum += nums[i];
if (sum > left_sum)
left_sum = sum;
}
sum = 0;
int right_sum = INT_MIN;
for (int i = m + 1; i <= h; i++) {
sum += nums[i];
if (sum > right_sum)
right_sum = sum;
}
return left_sum + right_sum;
}
int maxSubArraySum(vector<int>& nums, int l, int h) {
if (l == h)
return nums[l];
int m = (l + h) / 2;
int left_max = maxSubArraySum(nums, l, m);
int right_max = maxSubArraySum(nums, m + 1, h);
int cross_max = maxCrossingSum(nums, l, m, h);
return max(max(left_max, right_max), cross_max);
}
int main() {
vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int max_sum = maxSubArraySum(nums, 0, nums.size() - 1);
cout << "Maximum subarray sum is " << max_sum << endl;
return 0;
}function maxCrossingSum(arr, l, m, h) {
let leftSum = -Infinity;
let sum = 0;
for (let i = m; i >= l; i--) {
sum += arr[i];
if (sum > leftSum)
leftSum = sum;
}
let rightSum = -Infinity;
sum = 0;
for (let i = m + 1; i <= h; i++) {
sum += arr[i];
if (sum > rightSum)
rightSum = sum;
}
return leftSum + rightSum;
}
function maxSubArraySum(arr, l, h) {
if (l === h) {
return arr[l];
}
const mid = Math.floor((l + h) / 2);
const leftMax = maxSubArraySum(arr, l, mid);
const rightMax = maxSubArraySum(arr, mid + 1, h);
const crossMax = maxCrossingSum(arr, l, mid, h);
return Math.max(leftMax, rightMax, crossMax);
}
// Example usage
const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log("Maximum subarray sum is", maxSubArraySum(nums, 0, nums.length - 1));#include <stdio.h>
#include <limits.h>
int maxCrossingSum(int arr[], int l, int m, int h) {
int sum = 0;
int left_sum = INT_MIN;
for (int i = m; i >= l; i--) {
sum = sum + arr[i];
if (sum > left_sum)
left_sum = sum;
}
sum = 0;
int right_sum = INT_MIN;
for (int i = m + 1; i <= h; i++) {
sum = sum + arr[i];
if (sum > right_sum)
right_sum = sum;
}
return left_sum + right_sum;
}
int maxSubArraySum(int arr[], int l, int h) {
if (l == h)
return arr[l];
int m = (l + h) / 2;
int left_max = maxSubArraySum(arr, l, m);
int right_max = maxSubArraySum(arr, m + 1, h);
int cross_max = maxCrossingSum(arr, l, m, h);
return left_max > right_max ? (left_max > cross_max ? left_max : cross_max) : (right_max > cross_max ? right_max : cross_max);
}
int main() {
int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int size = sizeof(nums) / sizeof(nums[0]);
int max_sum = maxSubArraySum(nums, 0, size - 1);
printf("Maximum subarray sum is %d\n", max_sum);
return 0;
}using System;
public class MaxSubArrayDivideConquer {
public int MaxCrossingSum(int[] arr, int left, int mid, int right) {
int sum = 0;
int left_sum = Int32.MinValue;
for (int i = mid; i >= left; i--) {
sum += arr[i];
if (sum > left_sum)
left_sum = sum;
}
sum = 0;
int right_sum = Int32.MinValue;
for (int i = mid + 1; i <= right; i++) {
sum += arr[i];
if (sum > right_sum)
right_sum = sum;
}
return left_sum + right_sum;
}
public int MaxSubArraySum(int[] arr, int left, int right) {
if (left == right)
return arr[left];
int mid = (left + right) / 2;
int left_max = MaxSubArraySum(arr, left, mid);
int right_max = MaxSubArraySum(arr, mid + 1, right);
int cross_max = MaxCrossingSum(arr, left, mid, right);
return Math.Max(Math.Max(left_max, right_max), cross_max);
}
public static void Main(string[] args) {
MaxSubArrayDivideConquer solution = new MaxSubArrayDivideConquer();
int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
Console.WriteLine("Maximum subarray sum is " + solution.MaxSubArraySum(nums, 0, nums.Length - 1));
}
}This Python code uses a divide and conquer strategy, recursively calculating maximum subarray sums for the left, right, and crossing sections of the array. It combines these results to find the overall maximum subarray sum.
Time Complexity: O(n log n)
Space Complexity: O(log n) for the recursion stack
Approach 3: Dynamic Programming
We define f[i] to represent the maximum sum of a contiguous subarray ending at element nums[i]. Initially, f[0] = nums[0]. The final answer we seek is max_{0 leq i < n} f[i].
Consider f[i] for i geq 1. Its state transition equation is:
$
f[i] = max(f[i - 1] + nums[i], nums[i])
That is:
f[i] = max(f[i - 1], 0) + nums[i]
Since f[i] is only related to f[i - 1], we can use a single variable f to maintain the current value of f[i] and perform the state transition. The answer is max_{0 leq i < n} f.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1)$.
function maxSubArray(nums: number[]): number {
let [ans, f] = [nums[0], nums[0]];
for (let i = 1; i < nums.length; ++i) {
f = Math.max(f, 0) + nums[i];
ans = Math.max(ans, f);
}
return ans;
}func maxSubArray(nums []int) int {
ans, f := nums[0], nums[0]
for _, x := range nums[1:] {
f = max(f, 0) + x
ans = max(ans, f)
}
return ans
}impl Solution {
pub fn max_sub_array(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut ans = nums[0];
let mut f = nums[0];
for i in 1..n {
f = f.max(0) + nums[i];
ans = ans.max(f);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Kadane's Algorithm | Time Complexity: O(n) Space Complexity: O(1) |
| Approach 2: Divide and Conquer | Time Complexity: O(n log n) Space Complexity: O(log n) for the recursion stack |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Kadane's Algorithm | O(n) | O(1) | Best general solution. Preferred in interviews and production due to linear time and constant space. |
| Divide and Conquer | O(n log n) | O(log n) | Useful for understanding subarray boundaries and recursive problem decomposition. |
Frequently asked questions
Is Maximum Subarray easy or hard?
Maximum Subarray is generally considered a medium-level problem. The brute force idea is simple, but recognizing Kadane's Algorithm and understanding why resetting the running sum works requires algorithmic insight.
How to solve Maximum Subarray in O(n)?
Use Kadane's Algorithm. Maintain a running sum that represents the best subarray ending at the current index, calculated as max(nums[i], current_sum + nums[i]). Track the global maximum during iteration to get the final answer in linear time.
What is the best approach for Maximum Subarray?
Kadane's Algorithm is the best approach. It processes the array in a single pass while maintaining the maximum subarray ending at each position. The algorithm runs in O(n) time and O(1) space, which is optimal for this problem.
What data structure is used in Maximum Subarray?
The problem primarily uses an array as the input structure. The optimal solution does not require additional data structures, only a few variables to track running sums and the current maximum.
What is the time complexity of Maximum Subarray?
The optimal solution using Kadane's Algorithm runs in O(n) time because each element is processed exactly once. The divide and conquer approach runs in O(n log n) due to recursive splitting and merging of subarray results.
Maximum Subarray Python or Java solution approach?
Most Python and Java implementations use Kadane's Algorithm. Iterate through the array, update the running sum with max(current + num, num), and keep a global maximum variable. This keeps the implementation short and runs in O(n) time.
Is Maximum Subarray asked at Google, Amazon, or Meta?
Maximum Subarray is a classic interview problem frequently asked by companies like Google, Amazon, Meta, and Microsoft. It tests dynamic programming intuition, array manipulation, and the ability to optimize brute force approaches into linear-time solutions.