2026-08-11距离至少为 K 的交替子序列的最大和。用go语言给定一个整数数组和一个整数 k你需要从中挑选一个下标严格递增的子序列。挑选时必须满足相邻两个下标之差至少为 k。同时这些下标对应的数值必须构成一个严格交替的序列即要么按照“小、大、小、大……”的模式波动要么按照“大、小、大、小……”的模式波动相邻元素之间的大小关系交替变化且不能相等。只包含一个元素的子序列也视为合法交替。该子序列的得分定义为其中所有元素之和。请你计算在所有满足条件的子序列中能够获得的最大得分。1 n nums.length 100000。1 nums[i] 100000。1 k n。输入 nums [5,4,2], k 2。输出 7。解释一种最优选择是下标 [0, 2]对应的值为 [5, 2]。距离条件成立因为 2 - 0 2 k。这些值严格交替因为 5 2。得分为 5 2 7。题目来自力扣3915。大体步骤如下1. 值域离散化原数组中的数值范围可能较大最大到 100000但相对个数最多 100000直接按值建立树状数组会浪费空间。因此先将所有数值排序、去重得到一个紧凑的有序数组sorted。之后每个原始数值都可以用它在sorted中的下标即排名来表示排名从0到m-1m为不同值的个数。这样就将值域压缩到了[0, m-1]的整数范围便于树状数组处理。2. 定义状态对于每一个下标i定义两种状态fInc[i]以nums[i]结尾、且子序列最后两项呈现递增关系即前一个数 nums[i]的交替子序列的最大和。fDec[i]以nums[i]结尾、且子序列最后两项呈现递减关系即前一个数 nums[i]的交替子序列的最大和。长度为 1 的子序列既可以视为“递增结尾”也可以视为“递减结尾”其和就是nums[i]本身。这两种状态覆盖了所有可能的交替模式小大小大… 或 大小大小…。3. 初始化两个树状数组Fenwick Tree树状数组用于维护值域区间内的最大 DP 值支持单点取max更新和前缀最大值查询每次操作均为O(log m)。inc树状数组用于维护以递增结尾的状态fInc。为了能够方便地查询“值大于当前值”的所有状态它在内部对索引进行了反转映射。dec树状数组用于维护以递减结尾的状态fDec采用原值域顺序查询“值小于当前值”的状态。两个树状数组大小均为m1使用 1‑based 索引。4. 遍历数组动态规划转移按顺序遍历数组i 0到n-1对每个元素x nums[i]执行以下子步骤4.1 距离约束的“延迟加入”题目要求选中子序列的相邻下标之差 ≥ k。为了满足这一条件我们采用延迟激活的策略只有当i ≥ k时才将下标i-k对应的状态加入到树状数组中使其可以被当前及之后的下标使用。这保证了转移来源的原始下标与当前下标的距离至少为k。加入的具体操作为取出i-k位置已离散化的值j_prev该值在之前遍历时已被替换为排名。更新inc在位置m - j_prev上更新为max(原值, fInc[i-k])。这一步利用了反转索引把原本的“后缀查询”转化为树状数组擅长的“前缀查询”。更新dec在位置j_prev 1上更新为max(原值, fDec[i-k])。4.2 当前元素的离散化在当前元素x上使用二分查找得到其在sorted中的排名j0‑based。为了后续步骤ik能够直接使用该排名而无需再次二分将nums[i]就地修改为j因为原值之后不再需要。4.3 计算当前状态计算fInc[i]需要找一个前驱状态它必须是递减结尾fDec且其对应的值严格小于x即排名 j。在dec树状数组中查询前缀[1, j]对应排名≤ j-1的最大值加上x即可得到fInc[i]。若不存在这样的前驱查询返回0则fInc[i] x对应单元素子序列。计算fDec[i]需要找一个前驱状态它是递增结尾fInc且其值严格大于x即排名 j。通过反转索引在inc树状数组中查询前缀[1, m-1-j]对应排名≥ j1的最大值加上x得到fDec[i]。4.4 更新全局答案用刚刚算出的fInc[i]和fDec[i]去更新全局最大得分ans。5. 输出结果遍历完整个数组后ans即为所有满足条件的子序列的最大得分。复杂度分析时间复杂度离散化排序O(n log n)主循环执行n次每次包含一次二分查找O(log m)和两次树状数组操作更新/查询均为O(log m)。由于m ≤ n总时间复杂度为O(n log n)。额外空间复杂度离散化数组sorted占用O(m)DP 数组fInc和fDec各占用O(n)两个树状数组各占用O(m)。整体额外空间为O(n)。Go完整代码如下packagemainimport(fmtslicessort)typefenwick[]int64func(f fenwick)update(iint,valint64){for;ilen(f);ii-i{f[i]max(f[i],val)}}// [1, i] 中的最大值func(f fenwick)preMax(iint)(resint64){for;i0;ii-1{resmax(res,f[i])}return}funcmaxAlternatingSum(nums[]int,kint)(ansint64){// 离散化 numssorted:slices.Clone(nums)slices.Sort(sorted)sortedslices.Compact(sorted)n:len(nums)fInc:make([]int64,n)// fInc[i] 表示以 nums[i] 结尾且最后两项递增的交替子序列的最大和fDec:make([]int64,n)// fDec[i] 表示以 nums[i] 结尾且最后两项递减的交替子序列的最大和// 值域树状数组m:len(sorted)inc:make(fenwick,m1)// 维护 fInc[i] 的最大值dec:make(fenwick,m1)// 维护 fDec[i] 的最大值fori,x:rangenums{ifik{// 在这个时候才把 fInc[i-k] 和 fDec[i-k] 添加到值域树状数组中从而保证转移来源的下标 i-kj:nums[i-k]inc.update(m-j,fInc[i-k])// m-j 可以把后缀变成前缀dec.update(j1,fDec[i-k])}j:sort.SearchInts(sorted,x)nums[i]j// 注意这里修改了 nums[i]这样上面的 nums[i-k] 无需二分fInc[i]dec.preMax(j)int64(x)// 计算满足 nums[i] x 的 fDec[i] 的最大值fDec[i]inc.preMax(m-1-j)int64(x)// 计算满足 nums[i] x 的 fInc[i] 的最大值ansmax(ans,fInc[i],fDec[i])// 枚举子序列以 nums[i] 结尾}return}funcmain(){nums:[]int{5,4,2}k:2result:maxAlternatingSum(nums,k)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-fromtypingimportListimportbisectclassFenwick:树状数组维护前缀最大值1-indexeddef__init__(self,n:int):self.tree[0]*(n1)self.nndefupdate(self,i:int,val:int)-None:将位置 i 的值更新为 max(tree[i], val)whileiself.n:ifvalself.tree[i]:self.tree[i]val ii-idefpre_max(self,i:int)-int:查询 [1, i] 中的最大值res0whilei0:ifself.tree[i]res:resself.tree[i]ii-1returnresdefmax_alternating_sum(nums:List[int],k:int)-int:# 离散化获取去重排序后的数值sorted_numssorted(set(nums))mlen(sorted_nums)# 两个树状数组# inc 维护 f_inc以递增结尾的交替子序列最大和# dec 维护 f_dec以递减结尾的交替子序列最大和incFenwick(m)decFenwick(m)nlen(nums)f_inc[0]*n f_dec[0]*n ans0fori,xinenumerate(nums):# 只有当下标距离至少为 k 时才将 i-k 的状态加入树状数组ifik:j_prevnums[i-k]# 之前已经替换为离散化索引inc.update(m-j_prev,f_inc[i-k])dec.update(j_prev1,f_dec[i-k])# 当前元素离散化jbisect.bisect_left(sorted_nums,x)nums[i]j# 替换为索引供后续使用# 计算以当前元素结尾的两种状态# f_inc: 之前递减结尾且前一个数 当前数f_inc_idec.pre_max(j)x# f_dec: 之前递增结尾且前一个数 当前数f_dec_iinc.pre_max(m-1-j)x f_inc[i]f_inc_i f_dec[i]f_dec_iiff_inc_ians:ansf_inc_iiff_dec_ians:ansf_dec_ireturnansif__name____main__:nums[5,4,2]k2resultmax_alternating_sum(nums,k)print(result)C完整代码如下#includeiostream#includevector#includealgorithmusingnamespacestd;classFenwick{vectorlonglongtree;public:Fenwick(intn):tree(n1,0){}// 更新位置 i1-indexed的值为 max(tree[i], val)voidupdate(inti,longlongval){while(i(int)tree.size()){tree[i]max(tree[i],val);ii-i;}}// 查询前缀 [1, i] 的最大值longlongpreMax(inti)const{longlongres0;while(i0){resmax(res,tree[i]);ii-1;}returnres;}};longlongmaxAlternatingSum(vectorintnums,intk){// 离散化vectorintsortednums;sort(sorted.begin(),sorted.end());sorted.erase(unique(sorted.begin(),sorted.end()),sorted.end());intmsorted.size();intnnums.size();vectorlonglongfInc(n,0),fDec(n,0);// 注意初始化为 0空子序列和为 0Fenwickinc(m),dec(m);// 内部数组大小为 m1支持 1..m 索引longlongans0;for(inti0;in;i){intxnums[i];// 距离至少 k 时将 i-k 的状态加入树状数组if(ik){intj_prevnums[i-k];// 之前已替换为离散化索引inc.update(m-j_prev,fInc[i-k]);dec.update(j_prev1,fDec[i-k]);}// 当前元素的离散化索引intjlower_bound(sorted.begin(),sorted.end(),x)-sorted.begin();nums[i]j;// 替换原值后续直接使用索引// 状态转移fInc[i]dec.preMax(j)x;// 之前递减结尾且前一个数 当前数fDec[i]inc.preMax(m-1-j)x;// 之前递增结尾且前一个数 当前数ansmax({ans,fInc[i],fDec[i]});}returnans;}intmain(){vectorintnums{5,4,2};intk2;longlongresultmaxAlternatingSum(nums,k);coutresultendl;return0;}