Maximum Subarray#

Given an array of integers, find the contiguous subarray with the largest sum and return that sum. The subarray must contain at least one element, and the array can contain negative numbers.

Example#

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] Output: 6, from the subarray [4, -1, 2, 1].

Brute force#

Compute the sum of every possible subarray and keep the largest. Even with a running inner sum this is quadratic.

• Time: O(n^2).
• Space: O(1).

Optimal approach#

Use Kadane’s algorithm, a single-pass sliding sum. Walk the array keeping a running best sum that ends at the current position. At each step, either extend the previous run or start fresh at the current element, whichever is larger. Track the overall maximum across all positions. Starting fresh is the window sliding its left edge forward when the past run has become a drag.

Python solution#

1def max_sub_array(nums):
2    current = nums[0]
3    best = nums[0]
4    for num in nums[1:]:
5        current = max(num, current + num)
6        best = max(best, current)
7    return best

Complexity#

• Time: O(n), a single pass.
• Space: O(1), two running values.

This problem is the classic running-window optimization behind the sliding window technique. Keep going with the 60-day challenge.