{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Maximum Subarray – Solution & Complexity

Interview solutions
/
Maximum Subarray

1. Understand the Problem

  • We need the largest possible sum from one contiguous subarray.
  • The subarray must contain at least one number.
  • Negative numbers matter because the best answer could be a single negative element.

2. Start with a Brute Force Idea

  • Try every possible start and end index.
  • Compute each subarray sum and keep the largest.
  • This is correct but inefficient because there are O(n²) subarrays.
def max_sub_array(nums):
    best = nums[0]
    for start in range(len(nums)):
        total = 0
        for end in range(start, len(nums)):
            total += nums[end]
            best = max(best, total)
    return best

3. Key Insight: Keep the Best Ending Here

  • At each number, decide whether to extend the previous subarray or start fresh.
  • If the previous running sum is harmful, starting at the current number is better.
  • Track both the best sum ending at the current index and the best sum seen overall.

4. Apply Kadane's Algorithm

  • Initialize both values with the first element.
  • For every next number, update current to the better of starting new or extending.
  • Then update best with the larger value.
def max_sub_array(nums):
    current = nums[0]
    best = nums[0]
    for num in nums[1:]:
        current = max(num, current + num)
        best = max(best, current)
    return best

5. Final Solution and Complexity

  • Kadane's algorithm scans the array once.
  • Time complexity is O(n).
  • Space complexity is O(1) because only two running values are stored.
def max_sub_array(nums: list[int]) -> int:
    current = nums[0]
    best = nums[0]
    for num in nums[1:]:
        current = max(num, current + num)
        best = max(best, current)
    return best

FAQ

See also:

Practice Maximum Subarray online (run code in the browser)Best Time to Buy and Sell Stock solution (easy)Coin Change solution (medium)House Robber solution (medium)Jump Game solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?