#122: 延伸 - Kadane’s Algorithm,求最大區間和


rollfatcat (胖胖貓)

School : No School
ID : 378
IP address : [111.249.80.141]
Last Login :
2023-01-06 19:58:46
d051. P-4-12. 一次買賣 -- AP325 | From: [1.169.154.162] | Post Date : 2022-04-23 02:26

zerojudge 上的相似題: c435: MAX ! MAX ! MAX !

將相同的邏輯搭配前綴和的概念( 區間和轉換為兩數相減,只允許後面出現的減去前面的 )應用到解決求最大子區間和 - Kadane’s Algorithm

  • d784: 一、連續元素的和

  • a540: 10684 - The jackpot

  • b565: 5.採蘑菇攻略問題

將一維的概念推廣到二維:求矩陣範圍內的最大和

  • d206: 00108 - Maximum Sum

  • b840: 104北二4.農作物採收問題

  • d735: Minimum Sum

基於上述的最大子區間和的問題,再加上限制不超過K的情況後,就可以轉變為下述題目( 對照兩題,並知道為什麼方法不能互通 ):

  • d031: 例題 P-3-7. 正整數序列之最接近的區間和

  • d020: 例題 P-2-11. 最接近的區間和 (*)

一樣,將一維的概念推廣到二維:求矩陣範圍內的最大和:

  • d021: 習題 Q-2-12. 最接近的子矩陣和 (108 高中全國賽) (*)

  • f162: 4. 獵人與斯芬克斯

吳教授編寫的講義有詳細提到可以用 associative container 實現 O(logN) 插入和查詢熟悉分治法的 merge_sort - 過程中左右各半的數列保持單調性,可以藉此搭配 TwoPointer 搜尋左右邊各取一個數字相減接近K。

而利用分治法 (Divide & Conquer) 搭配記憶化處理(Memoization),可以再進一步延伸為歸併樹和劃分樹,求(靜態)區間第K大 或是 區間最大子區間和。

 

  • a164: 區間最大連續和

  • a331: K-th Number

 
ZeroJudge Forum