Maximum Contiguous Subarray Sum

Interview Problem Beginner Medium Array Dynamic Programming Kadane's Algorithm

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.maxSubArray(nums). nums is nonempty. Return the maximum sum of any contiguous nonempty subarray.

Starter code

class Solution:
    def maxSubArray(self, nums):
        pass

Test cases

mixed

{
  "args": [
    [
      -2,
      1,
      -3,
      4,
      -1,
      2,
      1,
      -5,
      4
    ]
  ]
}

Expected: 6

Wizard outline

Step 1: Initialize Solution.maxSubArray
Replace the empty starter with the first real state owned by Solution.maxSubArray. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Mixed case
Complete the readable core algorithm for one representative Interview case. Maintain the best subarray ending at the current position and the best seen globally.
Step 4: Harden the All Negative boundary
Repair the reviewed boundary and pass the complete submission contract. Any best subarray ending at the current value either contains only that value or extends the best subarray ending immediately before it. The global maximum over these ending states is the best subarray anywhere.

Footguns and prerequisites

Initializing the answer to zero incorrectly permits an empty subarray for all-negative input.
dynamic programming

Reviewed references

LeetCode 53 — Maximum Subarray

Practice prerequisites

Advance Kadane State(opens in a new tab)
Advance Kadane State isolates current equals the optimal non-empty sum ending at the current index, not the best sum anywhere in the processed prefix. That focused state discipline is required when implementing maximum subarray as a complete Interview Problem.

Recommended approach and implementation

For each value, choose between starting a new subarray there and extending the previous best-ending subarray.

Why it works: Any best subarray ending at the current value either contains only that value or extends the best subarray ending immediately before it. The global maximum over these ending states is the best subarray anywhere.

class Solution:
    def maxSubArray(self, nums):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        ending = best = nums[0]
        for value in nums[1:]:
            ending = max(value, ending + value)
            best = max(best, ending)
        return best