What pattern does Maximum Subarray use?

The Pattern: Dynamic Programming (Kadane's Algorithm) The Heuristic: The maximum subarray ending at position i either extends the maximum subarray ending at i-1 if that sum is positive, or starts fresh at i if the previous sum is negative or zero.

Maximum Subarray — Dynamic Programming

Q: What is the time complexity of Maximum Subarray?

O(n). The algorithm makes a single pass through the array, performing constant time operations per element.

Problem

Given an integer array nums, return the largest sum of a contiguous subarray.

1 ≤ nums.length ≤ 10⁵
−10⁴ ≤ nums[i] ≤ 10⁴

Example

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

Output: 6

The brute-force approach would check all possible subarrays and compute their sums, which is O(n²) and inefficient. The optimal solution uses a linear scan to track the maximum subarray sum ending at each position. Starting with current_sum = 0 and max_sum = nums[0], the algorithm iterates through nums, resetting current_sum to 0 whenever it becomes negative, then adds the current number. The max_sum is updated whenever current_sum exceeds it. For the example, the maximum subarray is [4,-1,2,1] with sum 6.

Approach

Straightforward Solution

A brute-force approach enumerates all subarrays and sums them, resulting in O(n²) time complexity, which is too slow for large inputs.

Core Observation

The maximum subarray sum ending at position i depends only on the maximum subarray sum ending at position i-1 and the current element nums[i]. If the previous sum is negative, it cannot contribute positively to the current sum, so it should be reset.

Path to Optimal

Preview

The key insight is to realize that if the running sum becomes negative, it should be discarded because continuing with a negative sum only decreases the total…

Full step-by-step walkthrough on Pro →

Optimal Approach

Iterate through the array once, maintaining a current_sum that resets to zero if negative, and a max_sum that tracks the highest sum seen so far. This approach guarantees O(n) time and O(1) space complexity.

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm makes a single pass through the array, performing constant time operations per element.

Space

O(1)

Only a fixed number of variables are used to track sums, regardless of input size.

Solution

Python

1class Solution:
  def maxSubArray(self, nums: list[int]) -> int:
      max_sum = nums[0]
      current_sum = 0
5
      for n in nums:
          if current_sum < 0:
              current_sum = 0
          current_sum += n
          max_sum = max(max_sum, current_sum)
      
      return max_sum

Step-by-Step Solution

1

Initialize Maximum and Current Subarray Sums

3max_sum = nums[0]
4current_sum = 0

Objective

To set up variables that track the maximum subarray sum found so far and the current running sum.

Key Insight

Initializing max_sum to the first element ensures that the algorithm correctly handles arrays with all negative numbers. Starting current_sum at zero allows the algorithm to accumulate sums and reset when negative.

Interview Quick-Check

Core Logic

max_sum starts as nums[0] to handle edge cases where all numbers are negative.

Common Pitfalls & Bugs

Initializing max_sum to zero instead of nums[0] can cause incorrect results when all elements are negative.

2

Iterate Through Array to Update Running and Maximum Sums

To scan through nums, accumulating sums and resetting when the running sum becomes negative, while tracking the maximum sum encountered.

3

Return the Maximum Subarray Sum Found

To output the largest sum of any contiguous subarray found during the iteration.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 7 Critical

if current_sum < 0:

Reset current_sum to zero if it is negative.

Discarding a negative current_sum prevents carrying forward a sum that would reduce the total of any future subarray, enabling optimal subarray detection.

Line 3 Critical

max_sum = nums[0]

Initialize max_sum to the first element of nums.

Setting max_sum to nums[0] ensures correct handling of arrays with all negative numbers, as it represents the best sum found so far.

Full line-by-line criticality + rationale for all 7 lines available on Pro.

Test Your Understanding

Why reset the current sum to zero when it becomes negative?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Maximum Subarray from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Maximum Subarray drill

or drill a free problem

1	`class Solution:`
2	`def maxSubArray(self, nums: list[int]) -> int:`
3	`max_sum = nums[0]`
4	`current_sum = 0`
5
6	`for n in nums:`
7	`if current_sum < 0:`
8	`current_sum = 0`
9	`current_sum += n`
10	`max_sum = max(max_sum, current_sum)`
11
12	`return max_sum`