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。具体步骤可以这样理解先固定一种操作模式比如“全部乘以 k”。然后再固定另一种模式“全部除以 k”。对每种模式分别求一个最大值最后比较两个最大值。在固定模式下从左到右遍历整个数组。对每个元素先根据模式计算出它被操作后的值如果是乘法模式操作后的值就是原值乘以 k。如果是除法模式操作后的值就是原值除以 k。除法要按题目要求取整数结果也就是向 0 方向截断。正数向下取整负数向上取整本质上就是直接丢弃小数部分保留靠近 0 的整数。扫描时维护三个状态分别表示以当前元素结尾的某种最大子数组和第一个状态还没有开始执行操作。这个状态只使用原值类似经典的最大子数组和。它可以随时放弃前面的负数部分从当前元素重新开始。第二个状态当前正处于操作区间内并且求和子数组也包含当前这个被操作的元素。这个状态使用操作后的值。它可以从“还没开始操作”的状态转移过来表示操作区间从当前元素开始也可以从自己上一轮的状态延续过来表示操作区间还在继续还可以直接丢弃前面从当前元素重新开始一个操作区间。第三个状态操作区间已经结束但求和子数组还在继续。这个状态使用原值。它只能从“正在操作”的状态转移过来表示操作刚刚结束或者从自己上一轮的状态延续过来表示操作早就结束了。每遍历一个元素更新这三个状态的顺序很关键先用上一轮的“正在操作”和“操作已结束”状态去更新新的“操作已结束”状态再用上一轮的“还没开始操作”和“正在操作”状态去更新新的“正在操作”状态最后用上一轮的“还没开始操作”状态去更新新的“还没开始操作”状态。这样做的目的是避免同一轮里状态互相覆盖保证每个状态用的都是上一轮的值。在每一步更新完之后用当前轮得到的“正在操作”状态和“操作已结束”状态去尝试更新全局最大值。为什么不直接考虑“还没开始操作”的状态因为题目要求必须执行一次操作最终求和子数组必须至少包含一个被乘过或除过的元素。只使用原值的子数组没有执行操作不符合要求。当整个数组扫描完一遍后就得到了这种操作模式下的最大可能和。然后换另一种操作模式再扫描一遍最后返回两种模式中的较大值。以示例 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完整代码如下packagemainimport(fmtmath)funcmaxSubarraySum(nums[]int,kint)int64{solve:func(isMulbool)int64{res:int64(math.MinInt)varf0,f1,f2int64for_,x:rangenums{x:int64(x)y:xifisMul{y*int64(k)}else{y/int64(k)}f2max(f1,f2)x f1max(f0,f1,0)y f0max(f0,0)x resmax(res,f1,f2)}returnres}returnmax(solve(true),solve(false))}funcmain(){nums:[]int{1,-2,3,4,-5}k:2result:maxSubarraySum(nums,k)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-fromtypingimportListdefmax_subarray_sum(nums:List[int],k:int)-int:deftrunc_div(a:int,b:int)-int:# Python 的 // 对负数向下取整这里改成向 0 取整ifa0:returna//breturn-((-a)//b)defsolve(is_mul:bool)-int:res-10**30f0f1f20forxinnums:yx*kifis_mulelsetrunc_div(x,k)f2max(f1,f2)x f1max(f0,f1,0)y f0max(f0,0)x resmax(res,f1,f2)returnresreturnmax(solve(True),solve(False))if__name____main__:nums[1,-2,3,4,-5]k2resultmax_subarray_sum(nums,k)print(result)C完整代码如下#includebits/stdc.husingnamespacestd;longlongmaxSubarraySum(vectorintnums,intk){autosolve[](boolisMul)-longlong{longlongresnumeric_limitslonglong::min();longlongf00,f10,f20;for(intv:nums){longlongxv;longlongyx;if(isMul){y*k;}else{// C 整数除法对负数也是向 0 截断符合题目要求y/k;}f2max(f1,f2)x;f1max({f0,f1,0LL})y;f0max(f0,0LL)x;resmax({res,f1,f2});}returnres;};returnmax(solve(true),solve(false));}intmain(){vectorintnums{1,-2,3,4,-5};intk2;longlongresultmaxSubarraySum(nums,k);coutresultendl;return0;}