经过一次操作后的最大子数组和 图解题解

必须挑一个元素平方，最大子数组和会怎么变

给一个整数数组 nums，必须挑恰好一个元素平方一次，再在改后数组里找一段非空连续子数组，让和最大。题面 nums=[2,-1,-4,-3]，把 -4 平方成 16、取 [2,-1,16]，和是 17。哪怕平方不划算，『必须』也得用掉这次操作。

枚举『平方哪个元素』，为什么要跑 n 遍扫描

『平方哪个元素』有 n 种选法：固定平方第 k 个，跑一遍普通最大子数组和，取最好。每种都要重扫数组，一趟 O(n)（大 O 记号，记操作数随数据量怎么涨），合计 O(n²)。这 n 遍只差平方位置，大量子段和被反复重算，该一遍扫描把两种情形一起管住。

两个状态 no 和 yes，各自记的是什么

关键是给『平方用没用掉』单独记账。开两个状态（DP，即动态规划，把『以第 i 位结尾、平方用/没用过的最大和』记下来后面直接接着用）：no 记以当前元素结尾、还没用平方的最大子段和，yes 同样以它结尾、但已用掉平方。拆开是因为『用没用过』决定还有没有资格再平方。题目必须平方，答案只从 yes 挑。

yes 为什么要在三条来路里挑最大

no 好办：以当前元素 x 结尾、不用平方，接前一段（no+x）或从 x 另起取大，这就是 Kadane（最大子数组和的经典扫法，每步只决定接前面还是另起）。yes 得盯『平方花在哪』，三条来路：平方早用在更前面，是 yes+x；平方正用在 x、前面接一段没平方的干净段，是 old_no + x²；平方用在 x 且前面不接，是 x²。取最大即新 yes。

第二、三条的 old_no 是命门：必须取『更新 no 之前』的旧值，每轮先存旧值再更新 no。

拿 [2,-1,-4,-3] 把两条账逐个元素填出来

起手 no=0（no 起手 0 是因为它允许空前缀、且答案不看 no），yes 和 ans 设成极小（还没有合法已平方段）。读 2：old_no=0，no=max(0+2, 2)=2，yes=max(极小+2, 0+4, 4)=4，ans=4。读 -1：old_no=2，no=max(2-1, -1)=1，yes=max(4-1, 2+1, 1)=3，ans 仍 4。读 -4：old_no=1，no=max(1-4, -4)=-3，yes=max(3-4, 1+16, 16)=17（平方花在 -4），ans 刷成 17。读 -3：old_no=-3，no=max(-3-3, -3)=-3，yes=max(17-3, -3+9, 9)=14，没超过 ans。扫完 ans=17，对上题面。

更新 yes 时用了刚改过的 no，这个数为什么被算了两次

病根在时序：old_no + x² 要的是『x 还没进账』的 no；先更新再配，x 被平方项和普通项各吃一次，yes 凭空变大。

复杂度：一趟循环，每元素几次比较加法，时间 O(n)；只留 no、yes、ans、old_no 几个变量轮换（只留最近用得上的值、覆盖旧的，叫滚动），空间 O(1)。答案只能取 yes 的全程最大——顺手返回 no 等于允许不平方，[2,-1,-4,-3] 会答成 2。单元素同样逃不掉：只有一个 -3 时答案是 9、不是 -3。

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 ans

C++

#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;
    }
}