LeetCode 题解工作台
找到最大非递减数组的长度
给你一个下标从 0 开始的整数数组 nums 。 你可以执行任意次操作。每次操作中，你需要选择一个 子数组 ，并将这个子数组用它所包含元素的 和 替换。比方说，给定数组是 [1,3,5,6] ，你可以选择子数组 [3,5] ，用子数组的和 8 替换掉子数组，然后数组会变为 [1,8,6] 。 请你返…
7
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
class Solution: def findMaximumLength(self, nums: List[int]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个下标从 0 开始的整数数组 nums 。
你可以执行任意次操作。每次操作中，你需要选择一个 子数组 ，并将这个子数组用它所包含元素的 和 替换。比方说，给定数组是 [1,3,5,6] ，你可以选择子数组 [3,5] ，用子数组的和 8 替换掉子数组，然后数组会变为 [1,8,6] 。
请你返回执行任意次操作以后，可以得到的 最长非递减 数组的长度。
子数组 指的是一个数组中一段连续 非空 的元素序列。
示例 1：
输入：nums = [5,2,2] 输出：1 解释：这个长度为 3 的数组不是非递减的。 我们有 2 种方案使数组长度为 2 。 第一种，选择子数组 [2,2] ，对数组执行操作后得到 [5,4] 。 第二种，选择子数组 [5,2] ，对数组执行操作后得到 [7,2] 。 这两种方案中，数组最后都不是 非递减 的，所以不是可行的答案。 如果我们选择子数组 [5,2,2] ，并将它替换为 [9] ，数组变成非递减的。 所以答案为 1 。
示例 2：
输入：nums = [1,2,3,4] 输出：4 解释：数组已经是非递减的。所以答案为 4 。
示例 3：
输入：nums = [4,3,2,6] 输出：3 解释：将 [3,2] 替换为 [5] ，得到数组 [4,5,6] ，它是非递减的。 最大可能的答案为 3 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 105
解题思路
方法一
class Solution:
def findMaximumLength(self, nums: List[int]) -> int:
n = len(nums)
s = list(accumulate(nums, initial=0))
f = [0] * (n + 1)
pre = [0] * (n + 2)
for i in range(1, n + 1):
pre[i] = max(pre[i], pre[i - 1])
f[i] = f[pre[i]] + 1
j = bisect_left(s, s[i] * 2 - s[pre[i]])
pre[j] = i
return f[n]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They want you to reframe repeated merge operations as partitioning nums into segment sums, not simulate array edits.
- question_mark
They are testing whether you can define a DP state that carries the last merged sum constraint forward.
- question_mark
They expect you to notice that brute-force split enumeration is the real bottleneck and replace it with prefix-sum search or a monotonic frontier.
常见陷阱
外企场景- error
Using LIS-style thinking on the original numbers instead of on merged segment sums leads to the wrong state definition for Find Maximum Non-decreasing Array Length.
- error
Tracking only dp[i] without the minimum valid last segment sum loses information and breaks future transitions.
- error
Implementing all j-to-i transitions directly causes quadratic time and will time out on large arrays.
进阶变体
外企场景- arrow_right_alt
Return the partition itself, not just the maximum length, which requires parent reconstruction on top of the DP transitions.
- arrow_right_alt
Change non-decreasing to strictly increasing, which tightens the transition inequality for the next segment sum.
- arrow_right_alt
Allow negative numbers, which makes some monotonic assumptions weaker and forces more careful transition handling.