Maximum Subarray

For Maximum Subarray, the core idea is simple: at each index, decide whether the best subarray ending here should continue the previous segment or start fresh from the current value. That state transition turns the problem into Kadane's algorithm, which runs in linear time and handles mixed positive and negative values cleanly. The main interview risk is updating the running answer incorrectly when all numbers are negative.

Problem Statement

You are given an integer array nums and need the largest possible sum from any non-empty contiguous subarray. The goal is not to pick scattered values, but to choose one continuous segment whose total is as large as possible and return that sum.

In the standard examples, nums = [-2,1,-3,4,-1,2,1,-5,4] returns 6 because [4,-1,2,1] is the best segment, nums = [1] returns 1, and nums = [5,4,-1,7,8] returns 23. Because nums can contain negative values and the array can be large, Maximum Subarray is really about tracking the best sum ending at each position without rechecking every subarray.

Examples

Example 1

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

The subarray [4,-1,2,1] has the largest sum 6.

Example 2

Input: nums = [1]

Output: 1

The subarray [1] has the largest sum 1.

Example 3

Input: nums = [5,4,-1,7,8]

Output: 23

The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

Solution Approach

Model the DP state as best sum ending at index i

The cleanest way to solve Maximum Subarray is to define a state for the best subarray sum that must end at the current index. For each value nums[i], either extend the previous subarray or drop it and start a new subarray at i. That gives the transition current = max(nums[i], current + nums[i]). While computing this state, keep a separate global best answer because the best subarray may end anywhere, not just at the final index.

Collapse the DP array into Kadane's algorithm

You do not need a full DP array because each Maximum Subarray transition depends only on the previous state. Store one running value for the best sum ending here and one running value for the best answer seen so far. This reduces space to O(1) and is the expected interview solution. On nums = [-2,1,-3,4,-1,2,1,-5,4], the key turning point is at 4, where restarting beats carrying the earlier negative prefix.

Know the divide and conquer alternative and its trade-off

Maximum Subarray also has a divide and conquer solution that combines the best left subarray, best right subarray, and best crossing subarray. That approach is useful when an interviewer wants to see the topic connection, but it is usually slower and more complex than Kadane's algorithm for direct coding. In practice, the DP state transition is the better execution choice because the failure mode is simpler: only the extend-versus-restart decision matters at each step.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

With the state transition dynamic programming approach, Maximum Subarray runs in O(n) time because each element is processed once, and O(1) extra space because only the previous ending sum and global best are stored. A divide and conquer version is typically O(n log n) time with recursive overhead, so it is mainly a topic extension rather than the best final implementation.

What Interviewers Usually Probe

• The interviewer emphasizes contiguous subarray, which usually points to tracking the best sum ending at each index rather than subset logic.
• They ask for a better solution after brute force, signaling Kadane's algorithm and the extend-or-restart state transition.
• They mention divide and conquer in follow-up discussion, which hints they want you to connect the optimal linear DP solution to the alternative recursive formulation.

Common Pitfalls or Variants

Common pitfalls

• Initializing the running answer to 0 breaks Maximum Subarray when all elements are negative, because the subarray must be non-empty.
• Confusing contiguous subarray with subsequence leads to illegal picks that skip negative values between positives.
• Updating the global best before applying the current extend-or-restart transition can miss the correct segment boundary.

Follow-up variants

• Return the start and end indices of the maximum subarray instead of only the sum, which adds boundary tracking to Kadane's transition.
• Solve the circular version where the best subarray may wrap from the end to the start, which changes how negative middle sections are treated.
• Use the divide and conquer formulation explicitly when asked to compute the best left, right, and crossing subarray sums.

FAQ

What is the fastest way to solve Maximum Subarray?

Use Kadane's algorithm. It applies the state transition current = max(nums[i], current + nums[i]) and keeps a separate global maximum, giving O(n) time and O(1) space.

Why does Maximum Subarray use state transition dynamic programming?

At each index, the best subarray ending there depends only on one previous fact: whether extending the earlier segment is better than starting fresh. That makes the recurrence local, which is exactly why this problem fits state transition dynamic programming.

How do you handle all-negative input in LeetCode 53?

Initialize both the running ending sum and the answer from the first element, not from 0. That preserves the required non-empty subarray and returns the largest negative value when every number is negative.

Is divide and conquer a valid solution for Maximum Subarray?

Yes. You can split the array and combine the best left subarray, best right subarray, and best crossing subarray. It is a valid approach, but it is usually less practical than the linear DP solution in interviews.

Why is brute force a poor fit for Maximum Subarray?

Brute force checks too many subarrays and does not use the key pattern of this problem: a negative running prefix should be discarded as soon as it hurts future sums. The DP transition captures that decision immediately in one pass.