zerojudge 上的相似題: c435: MAX ! MAX ! MAX !
將相同的邏輯搭配前綴和的概念( 區間和轉換為兩數相減,只允許後面出現的減去前面的 )應用到解決求最大子區間和 - Kadane’s Algorithm
將一維的概念推廣到二維:求矩陣範圍內的最大和
基於上述的最大子區間和的問題,再加上限制不超過K的情況後,就可以轉變為下述題目( 對照兩題,並知道為什麼方法不能互通 ):
一樣,將一維的概念推廣到二維:求矩陣範圍內的最大和:
吳教授編寫的講義有詳細提到可以用 associative container 實現 O(logN) 插入和查詢熟悉分治法的 merge_sort - 過程中左右各半的數列保持單調性,可以藉此搭配 TwoPointer 搜尋左右邊各取一個數字相減接近K。
而利用分治法 (Divide & Conquer) 搭配記憶化處理(Memoization),可以再進一步延伸為歸併樹和劃分樹,求(靜態)區間第K大 或是 區間最大子區間和。