Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Maximum Subarray

MEDIUMProblemSolveExternal Links

Description

You are given an integer array. Your task is to find the contiguous subarray (containing at least one element) that has the largest sum, and return that sum.

A subarray is a contiguous portion of the array — it consists of consecutive elements from the original array without skipping any. For example, in the array [1, -2, 3], the subarrays are [1], [-2], [3], [1, -2], [-2, 3], and [1, -2, 3].

The challenge lies in determining where to start and end the subarray to maximize the total sum, especially when the array contains a mix of positive and negative numbers.

Examples

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. Even though it includes the negative number -1, the surrounding positive values 4, 2, and 1 more than compensate: 4 + (-1) + 2 + 1 = 6. No other contiguous subarray produces a higher sum.

Example 2

Input: nums = [1]

Output: 1

Explanation: The array has only one element, so the only subarray is [1] with sum 1.

Example 3

Input: nums = [5, 4, -1, 7, 8]

Output: 23

Explanation: The entire array [5, 4, -1, 7, 8] has the largest sum: 5 + 4 + (-1) + 7 + 8 = 23. Even though -1 is negative, including it is worthwhile because the elements on both sides contribute enough positive value.

Example 4

Input: nums = [-3, -2, -1, -4]

Output: -1

Explanation: When all elements are negative, the maximum subarray is the single element closest to zero. Here, [-1] gives the maximum sum of -1. We cannot pick an empty subarray — at least one element must be included.

Constraints

  • 1 ≤ nums.length ≤ 10^5
  • -10^4 ≤ nums[i] ≤ 10^4

Editorial

Brute Force

Intuition

The most straightforward approach is to consider every possible subarray, compute its sum, and keep track of the maximum sum we find.

A subarray is defined by its starting index and ending index. So we can fix a starting index, then try every possible ending index from that start onward. For each combination of start and end, we compute the sum of all elements between them.

Imagine you have a row of numbered cards, some positive and some negative. To find the best contiguous hand, you could pick up every possible consecutive group of cards, add up their values, and remember which group gave you the highest total. This exhaustive search guarantees correctness but is slow because there are many possible groups to check.

Step-by-Step Explanation

Let's trace through with nums = [-2, 1, -3, 4, -1]:

Step 1: Initialize max_sum = -infinity. We start by considering all subarrays beginning at index 0.

Step 2: Subarray [0..0] = [-2], sum = -2. max_sum = max(-∞, -2) = -2.

Step 3: Subarray [0..1] = [-2, 1], sum = -2 + 1 = -1. max_sum = max(-2, -1) = -1.

Step 4: Subarray [0..2] = [-2, 1, -3], sum = -1 + (-3) = -4. max_sum stays -1.

Step 5: Subarray [0..3] = [-2, 1, -3, 4], sum = -4 + 4 = 0. max_sum stays -1.

Step 6: Subarray [0..4] = [-2, 1, -3, 4, -1], sum = 0 + (-1) = -1. max_sum stays -1.

Step 7: Move to subarrays starting at index 1. Subarray [1..1] = [1], sum = 1. max_sum = max(-1, 1) = 1.

Step 8: Subarray [1..2] = [1, -3], sum = 1 + (-3) = -2. max_sum stays 1.

Step 9: Subarray [1..3] = [1, -3, 4], sum = -2 + 4 = 2. max_sum = max(1, 2) = 2.

Step 10: Subarray [1..4] = [1, -3, 4, -1], sum = 2 + (-1) = 1. max_sum stays 2.

Step 11: Subarrays starting at index 2: [−3]=−3, [−3,4]=1, [−3,4,−1]=0. max_sum stays 2.

Step 12: Subarrays starting at index 3: [4]=4. max_sum = max(2, 4) = 4. [4,−1]=3. max_sum stays 4.

Step 13: Subarrays starting at index 4: [−1]=−1. max_sum stays 4.

Result: max_sum = 4 (subarray [4]).

Brute Force — Checking All Subarrays — Watch how we fix a starting index, then extend the ending index rightward to evaluate every possible subarray, tracking the running sum and global maximum.

Algorithm

  1. Initialize max_sum to negative infinity
  2. For each starting index i from 0 to n-1:
    a. Initialize current_sum = 0
    b. For each ending index j from i to n-1:
    • Add nums[j] to current_sum
    • Update max_sum = max(max_sum, current_sum)
  3. Return max_sum

Code

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int maxSum = INT_MIN;
        
        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            for (int j = i; j < n; j++) {
                currentSum += nums[j];
                maxSum = max(maxSum, currentSum);
            }
        }
        
        return maxSum;
    }
};
class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        n = len(nums)
        max_sum = float('-inf')
        
        for i in range(n):
            current_sum = 0
            for j in range(i, n):
                current_sum += nums[j]
                max_sum = max(max_sum, current_sum)
        
        return max_sum
class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int maxSum = Integer.MIN_VALUE;
        
        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            for (int j = i; j < n; j++) {
                currentSum += nums[j];
                maxSum = Math.max(maxSum, currentSum);
            }
        }
        
        return maxSum;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times and the inner loop runs up to n times for each outer iteration. The total number of subarray evaluations is n + (n-1) + (n-2) + ... + 1 = n(n+1)/2, which simplifies to O(n²). Each evaluation is O(1) since we maintain a running sum.

Space Complexity: O(1)

We only use two integer variables (maxSum and currentSum). No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force approach evaluates all O(n²) subarrays. With n up to 10^5, that means approximately 5 × 10^9 operations — well beyond the typical 10^8 operations-per-second limit for competitive programming judges.

The fundamental waste is that we keep restarting the sum computation from scratch for each new starting index. When we move from start=0 to start=1, we throw away all the work done for subarrays starting at 0, even though many of those computations overlap.

The key insight is this: at each position, we face a simple choice — should we extend the current subarray (by adding the current element) or start a new subarray from the current element? If the running sum of the subarray ending just before the current element is negative, it can only hurt us. Starting fresh is better. This observation leads to Kadane's algorithm, which solves the problem in a single pass.

Optimal Approach - Kadane's Algorithm

Intuition

Kadane's algorithm is based on a beautifully simple observation: at every position in the array, the maximum subarray ending at that position is either:

  1. The current element alone (starting a new subarray), or
  2. The current element plus the maximum subarray ending at the previous position (extending the existing subarray)

We choose whichever is larger. If the accumulated sum from previous elements is positive, it helps the current element — so we extend. If it is negative, it can only drag the sum down — so we start fresh.

Think of it like walking along a path collecting coins (positive numbers) and paying tolls (negative numbers). You carry a running total of your net gain. If your net gain ever becomes negative, you are better off dropping everything and starting over from the next coin — because the debt from past tolls would only reduce future earnings.

At every step, we also check if the current running sum is the best we have ever seen, and update our global maximum accordingly.

Step-by-Step Explanation

Let's trace through with nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

Step 1: Initialize current_sum = nums[0] = -2, max_sum = -2. The best subarray ending at index 0 is [-2].

Step 2: At index 1, nums[1] = 1. Should we extend or restart?

  • Extend: current_sum + 1 = -2 + 1 = -1
  • Restart: just 1
  • max(-1, 1) = 1 → Restart is better. current_sum = 1. The accumulated -2 was dragging us down.
  • max_sum = max(-2, 1) = 1.

Step 3: At index 2, nums[2] = -3.

  • Extend: 1 + (-3) = -2
  • Restart: -3
  • max(-2, -3) = -2 → Extend is better (less negative). current_sum = -2.
  • max_sum = max(1, -2) = 1. No improvement.

Step 4: At index 3, nums[3] = 4.

  • Extend: -2 + 4 = 2
  • Restart: 4
  • max(2, 4) = 4 → Restart is better. current_sum = 4. The previous sum of -2 would have reduced our 4.
  • max_sum = max(1, 4) = 4.

Step 5: At index 4, nums[4] = -1.

  • Extend: 4 + (-1) = 3
  • Restart: -1
  • max(3, -1) = 3 → Extend. current_sum = 3. The -1 hurts, but not enough to abandon the 4.
  • max_sum = max(4, 3) = 4. No improvement.

Step 6: At index 5, nums[5] = 2.

  • Extend: 3 + 2 = 5
  • Restart: 2
  • max(5, 2) = 5 → Extend. current_sum = 5.
  • max_sum = max(4, 5) = 5. New maximum!

Step 7: At index 6, nums[6] = 1.

  • Extend: 5 + 1 = 6
  • Restart: 1
  • max(6, 1) = 6 → Extend. current_sum = 6.
  • max_sum = max(5, 6) = 6. New maximum!

Step 8: At index 7, nums[7] = -5.

  • Extend: 6 + (-5) = 1
  • Restart: -5
  • max(1, -5) = 1 → Extend. current_sum = 1. The -5 is painful but we still have a positive running sum.
  • max_sum = max(6, 1) = 6. No improvement.

Step 9: At index 8, nums[8] = 4.

  • Extend: 1 + 4 = 5
  • Restart: 4
  • max(5, 4) = 5 → Extend. current_sum = 5.
  • max_sum = max(6, 5) = 6. No improvement.

Result: max_sum = 6, achieved by the subarray [4, -1, 2, 1].

Kadane's Algorithm — Extend or Restart Decision — Watch how at each position, we decide whether to extend the previous subarray or start fresh, based on whether the accumulated sum helps or hurts the current element.

Algorithm

  1. Initialize current_sum = nums[0] and max_sum = nums[0]
  2. For each element from index 1 to n-1:
    a. Set current_sum = max(nums[i], current_sum + nums[i])
    • If extending (current_sum + nums[i]) is better, extend the subarray
    • If starting fresh (nums[i] alone) is better, reset the subarray
      b. Set max_sum = max(max_sum, current_sum)
  3. Return max_sum

Code

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int currentSum = nums[0];
        int maxSum = nums[0];
        
        for (int i = 1; i < nums.size(); i++) {
            currentSum = max(nums[i], currentSum + nums[i]);
            maxSum = max(maxSum, currentSum);
        }
        
        return maxSum;
    }
};
class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        current_sum = nums[0]
        max_sum = nums[0]
        
        for i in range(1, len(nums)):
            current_sum = max(nums[i], current_sum + nums[i])
            max_sum = max(max_sum, current_sum)
        
        return max_sum
class Solution {
    public int maxSubArray(int[] nums) {
        int currentSum = nums[0];
        int maxSum = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return maxSum;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the array exactly once, visiting each of the n elements one time. At each element, we perform two constant-time max operations. Total work: n × O(1) = O(n).

Compared to the brute force O(n²), this is a dramatic improvement. For n = 10^5, we go from 5 × 10^9 operations to just 10^5 — a 50,000× speedup.

Space Complexity: O(1)

We use only two integer variables (currentSum and maxSum). No arrays, no hash maps, no recursion stack. The space usage is constant regardless of input size.