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.

#53

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。示例 1：输入： nums = [-2,1,-3,4,-1,2,1,-5,4] 输出： 6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 …

数组分治动态规划

题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i]$ 表示以元素 $\textit{nums}[i]$ 为结尾的连续子数组的最大和，初始时 $f[0] = \textit{nums}[0]$ ，那么最终我们要求的答案即为 $\max_{0 \leq i < n} f[i]$ 。

考虑 $f[i]$ ，其中 $i \geq 1$ ，它的状态转移方程为：

f[i] = \max(f[i - 1] + \textit{nums}[i], \textit{nums}[i])

也即：

f[i] = \max(f[i - 1], 0) + \textit{nums}[i]

由于 $f[i]$ 只与 $f[i - 1]$ 有关系，因此我们可以只用一个变量 $f$ 来维护对于当前 $f[i]$ 的值是多少，然后进行状态转移即可。答案为 $\max_{0 \leq i < n} f$ 。

时间复杂度 $O(n)$ ，其中 $n$ 为数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = f = nums[0]
        for x in nums[1:]:
            f = max(f, 0) + x
            ans = max(ans, f)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The interviewer emphasizes contiguous subarray, which usually points to tracking the best sum ending at each index rather than subset logic.
question_mark
They ask for a better solution after brute force, signaling Kadane's algorithm and the extend-or-restart state transition.
question_mark
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.

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#918 环形子数组的最大和 #55 跳跃游戏 #45 跳跃游戏 II