LeetCode 1746中等DP
经过一次操作后的最大子数组和 图解题解
这道题到底在问什么
给定整数数组 nums，必须选择其中一个元素平方一次。返回操作后某个非空连续子数组的最大和。
- 输入
- nums=[2,-1,-4,-3]
- 输出
- 17 （把 -4 平方成 16，子数组 [2,-1,16] 和为 17）
最优解：一步一步想明白
- 3记住「no 是普通最大子段和，yes 是已用平方的最大子段和，yes 取三种来法的最大」，下面每一帧都在套它。
- 4读第 0 个 2。先更新 no（没用平方的最大子段和）：从 2 自己重开更划算，no=2。
- 5更新 yes：把 2 平方成 4 最划算，yes=4（红色标出被平方的元素）。刷新 ans=4。
- 6读第 1 个 -1。先更新 no（没用平方的最大子段和）：接在前面后面更划算，no=2+-1=1。
- 7更新 yes：平方留在更早的位置、当前元素正常加进来更划算，yes=3。没超过 ans=4。
- 8读第 2 个 -4。先更新 no（没用平方的最大子段和）：接在前面后面更划算，no=1+-4=-3。
- 9更新 yes：把 -4 平方成 16 最划算，yes=17（红色标出被平方的元素）。刷新 ans=17。
- 10读第 3 个 -3。先更新 no（没用平方的最大子段和）：从 -3 自己重开更划算，no=-3。
- 11更新 yes：平方留在更早的位置、当前元素正常加进来更划算，yes=14。没超过 ans=17。
- 12读第 4 个 1。先更新 no（没用平方的最大子段和）：从 1 自己重开更划算，no=1。
- 13更新 yes：平方留在更早的位置、当前元素正常加进来更划算，yes=15。没超过 ans=17。
- 14读第 5 个 -5。先更新 no（没用平方的最大子段和）：接在前面后面更划算，no=1+-5=-4。
- 15更新 yes：把 -5 平方成 25 最划算，yes=26（红色标出被平方的元素）。刷新 ans=26。
- 16读第 6 个 2。先更新 no（没用平方的最大子段和）：从 2 自己重开更划算，no=2。
- 17更新 yes：平方留在更早的位置、当前元素正常加进来更划算，yes=28。刷新 ans=28。
- 18读第 7 个 3。先更新 no（没用平方的最大子段和）：接在前面后面更划算，no=2+3=5。
- 19更新 yes：平方留在更早的位置、当前元素正常加进来更划算，yes=31。刷新 ans=31。
- 20读第 8 个 -2。先更新 no（没用平方的最大子段和）：接在前面后面更划算，no=5+-2=3。
- 21更新 yes：平方留在更早的位置、当前元素正常加进来更划算，yes=29。没超过 ans=31。
- 22读第 9 个 4。先更新 no（没用平方的最大子段和）：接在前面后面更划算，no=3+4=7。
- 23更新 yes：平方留在更早的位置、当前元素正常加进来更划算，yes=33。刷新 ans=33。
- 24扫完全程，最优是绿色这段 [下标 4..9]，其中把红色的 nums[5]=-5 平方成 25，整段和 = 33。一遍扫描、两个状态就锁定了答案。
⚠️ 容易写错的地方
✗ 错：以为可以不平方
✓ 对：题目要求必须平方一次，答案只能从 yes 取
ans 取 yes 而非 no，否则会少算那次必须的操作
✗ 错：yes 只考虑 yes+x 一种来法
✓ 对：还要比 旧no+x² 和 x²
漏掉“在当前元素用平方”会错过把负数翻正的最优解
✗ 错：更新 yes 时用了已更新的 no
✓ 对：必须用本轮更新前的旧 no
旧no 才表示“当前元素之前都没用平方”
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def maxSumAfterOperation(self, nums: List[int]) -> int:
no = 0
yes = -10**30
ans = -10**30
for x in nums:
old_no = no
no = max(no + x, x)
yes = max(yes + x, old_no + x * x, x * x)
ans = max(ans, yes)
return ansC++
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
public:
int maxSumAfterOperation(vector<int>& nums) {
int no = 0, yes = INT_MIN / 4, ans = INT_MIN / 4;
for (int x : nums) {
int oldNo = no;
no = max(no + x, x);
yes = max({yes + x, oldNo + x * x, x * x});
ans = max(ans, yes);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int maxSumAfterOperation(int[] nums) {
int no = 0, yes = Integer.MIN_VALUE / 4, ans = Integer.MIN_VALUE / 4;
for (int x : nums) {
int oldNo = no;
no = Math.max(no + x, x);
yes = Math.max(Math.max(yes + x, oldNo + x * x), x * x);
ans = Math.max(ans, yes);
}
return ans;
}
}复杂度
时间
O(n)
扫一遍数组
空间
O(1)
只用 no、yes、ans 三个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 经过一次操作后的最大子数组和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这和普通最大子数组和（Kadane / LC53）什么关系？+
它就是 Kadane 加一维状态：no 完全是 LC53 的 Kadane；yes 多记“已用一次平方”的最优。把“是否已用某种一次性操作”作为额外维度，是一类 DP 的通用套路（股票冷冻期、一次翻转等都同构）。
如果是“最多平方一次”而非“必须平方一次”呢？+
那答案改成 max(no, yes)：no 覆盖“不平方”的情况，yes 覆盖“平方一次”的情况，取两者更大者即可。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 经过一次操作后的最大子数组和 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。