2026-10-01：乘以系数后最大子数组和。用go语言，输入包含一个整数序列 nums，以及一个大于零的整数 k。你需要先在 nums 中挑出一段连续

2026-10-01：乘以系数后最大子数组和。用go语言，输入包含一个整数序列 nums，以及一个大于零的整数 k。你需要先在 nums 中挑出一段连续且至少包含一个元素的范围，然后对这个范围里的所有数统一做两种处理之一：全部乘上 k，或者全部除以 k。做除法时，只保留整数结果，小数部分直接舍去，也就是朝 0 的方向取整。处理完成后会得到一个新的序列。接着，在这个新序列中再挑出一段连续且至少包含一个元素的范围，计算这段范围内所有数的和。第一步修改的范围和第二步求和的范围可以不同。问在所有可能选择中，这个和最大能是多少，并返回该最大值。

1 <= nums.length <= 100000。

-100000 <= nums[i] <= 100000。

1 <= k <= 100000。

输入： nums = [1,-2,3,4,-5], k = 2。

输出： 14。

解释：

将子数组 [3, 4] 中的每个数字乘以 2。

结果为 nums = [1, -2, 6, 8, -5]。

和最大的子数组是 [6, 8]，因此输出为 6 + 8 = 14。

题目来自力扣3976。

具体步骤可以这样理解：

1. 1. 先固定一种操作模式，比如“全部乘以 k”。
   然后再固定另一种模式“全部除以 k”。
   对每种模式分别求一个最大值，最后比较两个最大值。

2. 2. 在固定模式下，从左到右遍历整个数组。
   对每个元素，先根据模式计算出它被操作后的值：

• • 如果是乘法模式，操作后的值就是原值乘以 k。

• • 如果是除法模式，操作后的值就是原值除以 k。除法要按题目要求取整数结果，也就是向 0 方向截断。正数向下取整，负数向上取整，本质上就是直接丢弃小数部分，保留靠近 0 的整数。

3. 扫描时维护三个状态，分别表示以当前元素结尾的某种最大子数组和：

• • 第一个状态：还没有开始执行操作。这个状态只使用原值，类似经典的最大子数组和。它可以随时放弃前面的负数部分，从当前元素重新开始。

• • 第二个状态：当前正处于操作区间内，并且求和子数组也包含当前这个被操作的元素。这个状态使用操作后的值。它可以从“还没开始操作”的状态转移过来，表示操作区间从当前元素开始；也可以从自己上一轮的状态延续过来，表示操作区间还在继续；还可以直接丢弃前面，从当前元素重新开始一个操作区间。

• • 第三个状态：操作区间已经结束，但求和子数组还在继续。这个状态使用原值。它只能从“正在操作”的状态转移过来，表示操作刚刚结束；或者从自己上一轮的状态延续过来，表示操作早就结束了。

4. 每遍历一个元素，更新这三个状态的顺序很关键：
先用上一轮的“正在操作”和“操作已结束”状态去更新新的“操作已结束”状态；
再用上一轮的“还没开始操作”和“正在操作”状态去更新新的“正在操作”状态；
最后用上一轮的“还没开始操作”状态去更新新的“还没开始操作”状态。
这样做的目的是避免同一轮里状态互相覆盖，保证每个状态用的都是上一轮的值。

5. 在每一步更新完之后，用当前轮得到的“正在操作”状态和“操作已结束”状态去尝试更新全局最大值。
为什么不直接考虑“还没开始操作”的状态？因为题目要求必须执行一次操作，最终求和子数组必须至少包含一个被乘过或除过的元素。只使用原值的子数组没有执行操作，不符合要求。

6. 当整个数组扫描完一遍后，就得到了这种操作模式下的最大可能和。
然后换另一种操作模式再扫描一遍，最后返回两种模式中的较大值。

以示例 nums = [1, -2, 3, 4, -5]，k = 2 为例：
在乘法模式下，可以选择子数组 [3, 4] 乘以 2，数组变成 [1, -2, 6, 8, -5]。
此时和最大的子数组是 [6, 8]，和为 14。
除法模式不会得到更大的结果，所以最终答案是 14。

时间复杂度：
每种操作模式只需要从左到右扫描一次数组，乘法模式和除法模式各扫描一次，总共是两次线性扫描。因此总时间复杂度是 O(n)，其中 n 是 nums 的长度。

额外空间复杂度：
整个过程中只使用了常数个变量来保存三个状态和当前最大值，没有使用额外的数组或递归栈。因此总额外空间复杂度是 O(1)。

Go完整代码如下：

package main

 import (
    "fmt"
    "math"
)

 func maxSubarraySum(nums []int, k int)int64 {
    solve := func(isMul bool)int64 {
        res := int64(math.MinInt)
        var f0, f1, f2 int64
        for _, x := range nums {
            x := int64(x)
            y := x
            if isMul {
                y *= int64(k)
            } else {
                y /= int64(k)
            }
            f2 = max(f1, f2) + x
            f1 = max(f0, f1, 0) + y
            f0 = max(f0, 0) + x
            res = max(res, f1, f2)
        }
        return res
    }
    return max(solve(true), solve(false))
}

 func main() {
    nums := []int{1, -2, 3, 4, -5}
    k := 2
    result := maxSubarraySum(nums, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 from typing import List

 def max_subarray_sum(nums: List[int], k: int) -> int:
    def trunc_div(a: int, b: int) -> int:
        # Python 的 // 对负数向下取整，这里改成向 0 取整
        if a >= 0:
            return a // b
        return -((-a) // b)

     def solve(is_mul: bool) -> int:
        res = -10**30
        f0 = f1 = f2 = 0

         for x in nums:
            y = x * k if is_mul else trunc_div(x, k)

             f2 = max(f1, f2) + x
            f1 = max(f0, f1, 0) + y
            f0 = max(f0, 0) + x

             res = max(res, f1, f2)

         return res

     return max(solve(True), solve(False))

 if __name__ == "__main__":
    nums = [1, -2, 3, 4, -5]
    k = 2
    result = max_subarray_sum(nums, k)
    print(result)

C++完整代码如下：

  

using namespace std;

 long long maxSubarraySum(vector& nums, int k) {
    auto solve = [&](bool isMul) -> long long {
        long long res = numeric_limits 
 
 ::min(); 
 
        long long f0 = 0, f1 = 0, f2 = 0;

         for (int v : nums) {
            long long x = v;
            long long y = x;

             if (isMul) {
                y *= k;
            } else {
                // C++ 整数除法对负数也是向 0 截断，符合题目要求
                y /= k;
            }

             f2 = max(f1, f2) + x;
            f1 = max({f0, f1, 0LL}) + y;
            f0 = max(f0, 0LL) + x;

             res = max({res, f1, f2});
        }

         return res;
    };

     return max(solve(true), solve(false));
}

 int main() {
    vector nums = {1, -2, 3, 4, -5};
    int k = 2;

     long long result = maxSubarraySum(nums, k);
    cout << result << endl;

     return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。