Maximum Subarray

Difficulty: Medium

Problem

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example

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.

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)