ABC095 D Static Sushi
寿司のとり方として最適なのは時計回りに
$ i
個, 反時計回りに
$ j
個それぞれ連続してとることである(ただし
$ i + j \leq n
). ここで一方を固定することを考える. するともう一方は差し引きカロリー摂取量が最大となるように貪欲に選べばよく, これは累積maxを前計算しておくことにより高速に求められる. 計算量は
$ O(N)
となる.
実装例:
https://atcoder.jp/contests/abc095/submissions/20568849