Maximum Subarray

Approach Summary

Kadane's: at each position, current max = max(num, prevMax + num). Global max tracked throughout.

Full Solution & Approach

Kadane's algorithm maintains the best subarray sum that ends at the current position. Two observations make it work: (1) the maximum subarray either extends the previous best or starts fresh at the current element, and (2) if a running sum ever drops below the current element alone, starting over beats carrying the negative prefix. So keep cur = max(nums[i], cur + nums[i]) and track the overall best = max(best, cur). When cur + nums[i] is worse than nums[i], the previous window is discarded — this implicitly handles the all-negative case, where the answer is simply the largest single element. Because the running sum depends only on the previous step, the algorithm is a single pass with O(1) space. The divide-and-conquer variant exists, but Kadane's is simpler and the one expected in interviews.

Single pass over n elements with constant work per element — O(n) time. Two scalar variables — O(1) space.

Solution Code

Solution

def max_sub_array(nums: list[int]) -> int:
    best = cur = nums[0]
    for n in nums[1:]:
        cur = max(n, cur + n)
        best = max(best, cur)
    return best

function maxSubArray(nums) {
  let best = nums[0], cur = nums[0];
  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]);
    best = Math.max(best, cur);
  }
  return best;
}

public int maxSubArray(int[] nums) {
    int best = nums[0], cur = nums[0];
    for (int i = 1; i < nums.length; i++) {
        cur = Math.max(nums[i], cur + nums[i]);
        best = Math.max(best, cur);
    }
    return best;
}

int maxSubArray(const vector<int>& nums) {
    int best = nums[0], cur = nums[0];
    for (int i = 1; i < (int)nums.size(); i++) {
        cur = max(nums[i], cur + nums[i]);
        best = max(best, cur);
    }
    return best;
}

Edge Cases to Watch

All negative numbers — Kadane's resets at every element and returns the largest single value
Single element — best = nums[0]
Zeros and negative values mixed — the reset logic handles them naturally

How to Recognize This Pattern

Maximum sum subarray
Kadane's algorithm

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)