Maximum Subarray: Kadane's Algorithm as One Line of DP

"Maximum Subarray" shows up again and again in Amazon, Microsoft, LinkedIn phone screens. It is a Medium problem on paper, but the real test is whether you recognize the Dynamic Programming pattern quickly and code it cleanly. Part 2 of 11 in the Dynamic Programming arc.

The Problem

Find the contiguous subarray with the largest sum and return that sum. Among the most-asked array questions in existence, and the cleanest example of a state refinement: the trick is not 'best so far' but 'best ending here'.

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

Recognizing the Dynamic Programming Pattern

Dynamic programming is recursion with the repetition removed: define the answer to a subproblem, express it in terms of smaller subproblems, and compute each exactly once — top-down with memoization or bottom-up with a table. In interviews the grade hinges on the state definition said out loud ('dp[i] is the best answer using the first i items') far more than on the loop that follows. Most FAANG DP questions are one-dimensional or a small 2D grid — the nine below cover the shapes that repeat.

Best over all subarrays becomes tractable when indexed by endpoint: the best subarray ending at i either extends the best ending at i−1 or restarts at i — whichever is larger. A max over a refined, endpoint-indexed state is a recurring DP design move (Longest Increasing Subsequence uses it too).

The Approach

Sweep once holding ending_here (max of the element alone vs extending) and the global best. All-negative arrays fall out correctly because restart happens at every step and the best single element wins.

Say 'Kadane's algorithm is DP with the table collapsed' — it positions you as understanding rather than reciting, and sets up the divide-and-conquer follow-up (the LeetCode footnote) if it comes.

Python Solution

def max_subarray(nums: list[int]) -> int:
    """Largest sum over all contiguous subarrays (Kadane)."""
    ending_here = best = nums[0]
    for x in nums[1:]:
        ending_here = max(x, ending_here + x)   # extend or restart
        best = max(best, ending_here)
    return best

Complexity

• Time: O(n) — single pass
• Space: O(1) — two scalars

Interview Tips and Follow-Ups

• All-negative input is the planted case — initializing best at 0 fails it; initialize from nums[0]. Volunteer this before running anything.
• Returning the subarray itself: track the restart index alongside — a 60-second extension worth pre-thinking.
• The circular variant (Maximum Sum Circular Subarray) is Kadane plus total-minus-minimum-subarray — a favorite Amazon escalation.

That wraps part 2 of the Dynamic Programming arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.