{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Maximum Subarray – Solution & Complexity

Interview solutions
/
Maximum Subarray
Quick practice for Maximum Subarray: 3 reasoning beats, no typing

Watch: Maximum Subarray with Kadane's algorithm

At each number, decide whether to extend the current run or start fresh. If the running sum has gone negative, it can only drag the next number down, so drop it. Track the best sum seen. O(n) time, O(1) space.

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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. Step 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)House Robber II solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?