首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C >> 關於C

HDU 5586:SUM——最大子段和變體(一次區間函數變換最大化總和)

     編輯:關於C

題目大意

給定長度n(≤10^5)數列a[i],可選擇一個區間[l,r](或不選),將區間內每個元素a[i]替換為f(a[i])(題中隱含f(x)=10007-x mod 10007等特定函數)。求操作後數列總和的最大值。

轉化為最大子段和問題

設原數列總和為S = Σa[i]。
對區間[l,r]操作後,總和變化量為Δ = Σ_{i=l}^r (f(a[i]) - a[i])。
定義差值數組d[i] = f(a[i]) - a[i]。
問題轉化為:求d數組的最大子段和(可為空,即不操作)。
答案 = S + max(0, maxSubArraySum(d))。

算法:Kadane算法 O(n)

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved