Maximum Subarray

Difficulty: Medium

Problem

Given an integer array nums (values may be negative), pick a non-empty run of adjacent elements whose total is as large as possible, and return that total.

Example

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: The run [4, -1, 2, 1] adds up to 6, which beats every other run of adjacent elements.

Brute-force approach

Check every possible subarray by trying all start and end positions, calculating each sum.

Steps

  1. Try every starting position
  2. Try every ending position after start
  3. Calculate sum of each subarray
  4. Track the maximum sum found

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • Checks many overlapping subarrays redundantly
  • Recalculates sums that share common elements
  • Quadratic time is slow for large arrays

Optimal approach

Key insight: At each index, the max subarray ending here is either: just this element alone, or this element plus the max subarray ending at the previous index.

Kadane's Algorithm: at each position, decide whether to extend the current subarray or start fresh from the current element.

Steps

  1. Track current sum and max sum
  2. At each element: decide extend or restart
  3. Update maxSum if currentSum is larger
  4. Return maxSum

Time complexity: O(n) · Space complexity: O(1)

Pseudocode

function maxSubArray(nums):
    maxSum = nums[0]
    currentSum = nums[0]
    
    for i from 1 to length of nums:
        currentSum = max(nums[i], currentSum + nums[i])
        maxSum = max(maxSum, currentSum)
    
    return maxSum

Hints

  • This is Kadane's algorithm
  • At each position, decide: start fresh or extend the current subarray?
  • Track both the current running sum and the best sum seen so far

Complexity questions

Time to check all subarrays?

O(n²). With running sum optimization: O(n²) for all start/end pairs

Time complexity of Kadane's Algorithm?

O(n). One pass through array, constant work per element = O(n)

Space complexity of Kadane's Algorithm?

O(1). Only two variables: currentSum and maxSum = O(1)

What makes Kadane's algorithm efficient?

Dynamic programming with optimal substructure. It uses optimal substructure: the best solution at i depends only on the best at i-1

Check your understanding of Maximum Subarray

What is a subarray?

A contiguous portion of the array. A subarray is a contiguous (consecutive) portion of the array. Elements must be next to each other.

Given nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4], what subarray has the maximum sum?

[4, -1, 2, 1]. The subarray [4, -1, 2, 1] has sum 4 + (-1) + 2 + 1 = 6, which is the maximum.

What should be returned for the Maximum Subarray problem?

The sum of the maximum subarray. We return the SUM of the maximum subarray, not the subarray itself.

Related problems

Keep practising