2026-08-11距離至少為 K 的交替子序列的最大和。用go語言給定一個整數(shù)數(shù)組和一個整數(shù) k你需要從中挑選一個下標(biāo)嚴(yán)格遞增的子序列。挑選時必須滿足相鄰兩個下標(biāo)之差至少為 k。同時這些下標(biāo)對應(yīng)的數(shù)值必須構(gòu)成一個嚴(yán)格交替的序列即要么按照“小、大、小、大……”的模式波動要么按照“大、小、大、小……”的模式波動相鄰元素之間的大小關(guān)系交替變化且不能相等。只包含一個元素的子序列也視為合法交替。該子序列的得分定義為其中所有元素之和。請你計算在所有滿足條件的子序列中能夠獲得的最大得分。1 n nums.length 100000。1 nums[i] 100000。1 k n。輸入 nums [5,4,2], k 2。輸出 7。解釋一種最優(yōu)選擇是下標(biāo) [0, 2]對應(yīng)的值為 [5, 2]。距離條件成立因為 2 - 0 2 k。這些值嚴(yán)格交替因為 5 2。得分為 5 2 7。題目來自力扣3915。大體步驟如下1. 值域離散化原數(shù)組中的數(shù)值范圍可能較大最大到 100000但相對個數(shù)最多 100000直接按值建立樹狀數(shù)組會浪費空間。因此先將所有數(shù)值排序、去重得到一個緊湊的有序數(shù)組sorted。之后每個原始數(shù)值都可以用它在sorted中的下標(biāo)即排名來表示排名從0到m-1m為不同值的個數(shù)。這樣就將值域壓縮到了[0, m-1]的整數(shù)范圍便于樹狀數(shù)組處理。2. 定義狀態(tài)對于每一個下標(biāo)i定義兩種狀態(tài)fInc[i]以nums[i]結(jié)尾、且子序列最后兩項呈現(xiàn)遞增關(guān)系即前一個數(shù) nums[i]的交替子序列的最大和。fDec[i]以nums[i]結(jié)尾、且子序列最后兩項呈現(xiàn)遞減關(guān)系即前一個數(shù) nums[i]的交替子序列的最大和。長度為 1 的子序列既可以視為“遞增結(jié)尾”也可以視為“遞減結(jié)尾”其和就是nums[i]本身。這兩種狀態(tài)覆蓋了所有可能的交替模式小大小大… 或 大小大小…。3. 初始化兩個樹狀數(shù)組Fenwick Tree樹狀數(shù)組用于維護(hù)值域區(qū)間內(nèi)的最大 DP 值支持單點取max更新和前綴最大值查詢每次操作均為O(log m)。inc樹狀數(shù)組用于維護(hù)以遞增結(jié)尾的狀態(tài)fInc。為了能夠方便地查詢“值大于當(dāng)前值”的所有狀態(tài)它在內(nèi)部對索引進(jìn)行了反轉(zhuǎn)映射。dec樹狀數(shù)組用于維護(hù)以遞減結(jié)尾的狀態(tài)fDec采用原值域順序查詢“值小于當(dāng)前值”的狀態(tài)。兩個樹狀數(shù)組大小均為m1使用 1?based 索引。4. 遍歷數(shù)組動態(tài)規(guī)劃轉(zhuǎn)移按順序遍歷數(shù)組i 0到n-1對每個元素x nums[i]執(zhí)行以下子步驟4.1 距離約束的“延遲加入”題目要求選中子序列的相鄰下標(biāo)之差 ≥ k。為了滿足這一條件我們采用延遲激活的策略只有當(dāng)i ≥ k時才將下標(biāo)i-k對應(yīng)的狀態(tài)加入到樹狀數(shù)組中使其可以被當(dāng)前及之后的下標(biāo)使用。這保證了轉(zhuǎn)移來源的原始下標(biāo)與當(dāng)前下標(biāo)的距離至少為k。加入的具體操作為取出i-k位置已離散化的值j_prev該值在之前遍歷時已被替換為排名。更新inc在位置m - j_prev上更新為max(原值, fInc[i-k])。這一步利用了反轉(zhuǎn)索引把原本的“后綴查詢”轉(zhuǎn)化為樹狀數(shù)組擅長的“前綴查詢”。更新dec在位置j_prev 1上更新為max(原值, fDec[i-k])。4.2 當(dāng)前元素的離散化在當(dāng)前元素x上使用二分查找得到其在sorted中的排名j0?based。為了后續(xù)步驟ik能夠直接使用該排名而無需再次二分將nums[i]就地修改為j因為原值之后不再需要。4.3 計算當(dāng)前狀態(tài)計算fInc[i]需要找一個前驅(qū)狀態(tài)它必須是遞減結(jié)尾fDec且其對應(yīng)的值嚴(yán)格小于x即排名 j。在dec樹狀數(shù)組中查詢前綴[1, j]對應(yīng)排名≤ j-1的最大值加上x即可得到fInc[i]。若不存在這樣的前驅(qū)查詢返回0則fInc[i] x對應(yīng)單元素子序列。計算fDec[i]需要找一個前驅(qū)狀態(tài)它是遞增結(jié)尾fInc且其值嚴(yán)格大于x即排名 j。通過反轉(zhuǎn)索引在inc樹狀數(shù)組中查詢前綴[1, m-1-j]對應(yīng)排名≥ j1的最大值加上x得到fDec[i]。4.4 更新全局答案用剛剛算出的fInc[i]和fDec[i]去更新全局最大得分ans。5. 輸出結(jié)果遍歷完整個數(shù)組后ans即為所有滿足條件的子序列的最大得分。復(fù)雜度分析時間復(fù)雜度離散化排序O(n log n)主循環(huán)執(zhí)行n次每次包含一次二分查找O(log m)和兩次樹狀數(shù)組操作更新/查詢均為O(log m)。由于m ≤ n總時間復(fù)雜度為O(n log n)。額外空間復(fù)雜度離散化數(shù)組sorted占用O(m)DP 數(shù)組fInc和fDec各占用O(n)兩個樹狀數(shù)組各占用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] 結(jié)尾且最后兩項遞增的交替子序列的最大和fDec:make([]int64,n)// fDec[i] 表示以 nums[i] 結(jié)尾且最后兩項遞減的交替子序列的最大和// 值域樹狀數(shù)組m:len(sorted)inc:make(fenwick,m1)// 維護(hù) fInc[i] 的最大值dec:make(fenwick,m1)// 維護(hù) fDec[i] 的最大值fori,x:rangenums{ifik{// 在這個時候才把 fInc[i-k] 和 fDec[i-k] 添加到值域樹狀數(shù)組中從而保證轉(zhuǎn)移來源的下標(biāo) 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] 結(jié)尾}return}funcmain(){nums:[]int{5,4,2}k:2result:maxAlternatingSum(nums,k)fmt.Println(result)}Python完整代碼如下# -*-coding:utf-8-*-fromtypingimportListimportbisectclassFenwick:樹狀數(shù)組維護(hù)前綴最大值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:# 離散化獲取去重排序后的數(shù)值sorted_numssorted(set(nums))mlen(sorted_nums)# 兩個樹狀數(shù)組# inc 維護(hù) f_inc以遞增結(jié)尾的交替子序列最大和# dec 維護(hù) f_dec以遞減結(jié)尾的交替子序列最大和incFenwick(m)decFenwick(m)nlen(nums)f_inc[0]*n f_dec[0]*n ans0fori,xinenumerate(nums):# 只有當(dāng)下標(biāo)距離至少為 k 時才將 i-k 的狀態(tài)加入樹狀數(shù)組ifik:j_prevnums[i-k]# 之前已經(jīng)替換為離散化索引inc.update(m-j_prev,f_inc[i-k])dec.update(j_prev1,f_dec[i-k])# 當(dāng)前元素離散化jbisect.bisect_left(sorted_nums,x)nums[i]j# 替換為索引供后續(xù)使用# 計算以當(dāng)前元素結(jié)尾的兩種狀態(tài)# f_inc: 之前遞減結(jié)尾且前一個數(shù) 當(dāng)前數(shù)f_inc_idec.pre_max(j)x# f_dec: 之前遞增結(jié)尾且前一個數(shù) 當(dāng)前數(shù)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);// 內(nèi)部數(shù)組大小為 m1支持 1..m 索引longlongans0;for(inti0;in;i){intxnums[i];// 距離至少 k 時將 i-k 的狀態(tài)加入樹狀數(shù)組if(ik){intj_prevnums[i-k];// 之前已替換為離散化索引inc.update(m-j_prev,fInc[i-k]);dec.update(j_prev1,fDec[i-k]);}// 當(dāng)前元素的離散化索引intjlower_bound(sorted.begin(),sorted.end(),x)-sorted.begin();nums[i]j;// 替換原值后續(xù)直接使用索引// 狀態(tài)轉(zhuǎn)移fInc[i]dec.preMax(j)x;// 之前遞減結(jié)尾且前一個數(shù) 當(dāng)前數(shù)fDec[i]inc.preMax(m-1-j)x;// 之前遞增結(jié)尾且前一個數(shù) 當(dāng)前數(shù)ansmax({ans,fInc[i],fDec[i]});}returnans;}intmain(){vectorintnums{5,4,2};intk2;longlongresultmaxAlternatingSum(nums,k);coutresultendl;return0;}