Maximum Subarray

Difficulty: Medium Source: NeetCode

Problem

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

Example 1: Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] Output: 6 Explanation: The subarray [4, -1, 2, 1] has sum 6.

Example 2: Input: nums = [1] Output: 1

Example 3: Input: nums = [5, 4, -1, 7, 8] Output: 23

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

Prerequisites

Before attempting this problem, you should be comfortable with:

• Greedy thinking — knowing when to abandon a running sum
• Dynamic programming basics — dp[i] in terms of dp[i-1]

1. Brute Force

Intuition

Try every possible subarray. For each starting index i, compute the sum of all subarrays starting at i and track the maximum. This is O(n²) — correct but slow.

Algorithm

1. Initialise max_sum = -infinity.
2. For each i from 0 to n-1:
   • running = 0
   • For each j from i to n-1:
     • running += nums[j]
     • max_sum = max(max_sum, running)
3. Return max_sum.

Solution

def maxSubArray(nums):
    max_sum = float('-inf')
    for i in range(len(nums)):
        running = 0
        for j in range(i, len(nums)):
            running += nums[j]
            max_sum = max(max_sum, running)
    return max_sum


print(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6
print(maxSubArray([1]))                                 # 1
print(maxSubArray([5, 4, -1, 7, 8]))                   # 23
print(maxSubArray([-1, -2, -3]))                        # -1

Complexity

• Time: O(n²)
• Space: O(1)

2. Kadane’s Algorithm (Greedy / DP)

Intuition

At each index, decide: should we extend the current subarray or start a new one here? If the current running sum is negative, it can only drag down any future subarray — so we drop it and restart from the current element. Otherwise, we extend. This greedy decision is optimal: a negative prefix never helps.

More formally, dp[i] = max(nums[i], dp[i-1] + nums[i]). We only need the previous value, so we use a single variable.

Algorithm

1. Initialise current = nums[0], max_sum = nums[0].
2. For each num in nums[1:]:
   • current = max(num, current + num) — start fresh or extend.
   • max_sum = max(max_sum, current).
3. Return max_sum.

Solution

def maxSubArray(nums):
    current = nums[0]
    max_sum = nums[0]

    for num in nums[1:]:
        current = max(num, current + num)
        max_sum = max(max_sum, current)

    return max_sum


print(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6
print(maxSubArray([1]))                                 # 1
print(maxSubArray([5, 4, -1, 7, 8]))                   # 23
print(maxSubArray([-1, -2, -3]))                        # -1
print(maxSubArray([-2, -1]))                            # -1


# Equivalent formulation: drop the prefix when it goes negative
def maxSubArray_v2(nums):
    max_sum = nums[0]
    current = 0

    for num in nums:
        current += num
        max_sum = max(max_sum, current)
        if current < 0:
            current = 0  # reset: negative prefix helps nobody

    return max_sum


print(maxSubArray_v2([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6

Complexity

• Time: O(n)
• Space: O(1)

Common Pitfalls

Initialising max_sum = 0. If all elements are negative, the best subarray is the single largest element. Starting at 0 would incorrectly return 0 for an all-negative array. Always initialise with nums[0] or -infinity.

Resetting current to 0 but forgetting to update max_sum first. In the “reset on negative” variant, update max_sum = max(max_sum, current) before resetting current. Otherwise you’ll miss the max that occurred just before the reset.

Confusing this with Maximum Subarray Sum with No Adjacent Elements. That’s a different problem (house robber variant). This problem allows any contiguous subarray, including one of length 1.