Codeforces #33 C Wonderful Randomized Sum

題目簡單，問的是給出一個整數陣列A，取任意一前綴各項乘-1，取任意一後綴各項乘一，問兩個操作後A的所有元素和最大是多少？前後綴長度可以為零。

我花了點時間還是做不到，故看了某blog的解題，其實方法也是用如前幾篇文章所述的Relax法去解題。

Relax﹕如果只允許取前綴的話，那麼最大和是多少？

答案是比較簡單的，只需計算 max{Sum[1..N] - 2 * Sum[1..i], Sum[1..N]}即可，注意第二個參數是代表不取任何前綴之和。留意該公式只有Sum[1..i]是有變化的，故可重寫成Sum[0..N] - min{Sum[0..i]}, 當中設A[0] = 0。故只需O(N)預計算Sum[0..i]，後取k令Sum[0..k]最小者即可。答案即 Sum[0..N] - 2 * Sum[0..k]。

那麼對於A的長度為N的答案我們可以用P[N]來紀錄，即P[N] = i。

Observation 1﹕ P[i] <= P[i+1]。
這是我們取P[N]的時候的by-product而已，同樣可以看作把Relax問題放到A[1..i]然後取P[i]。

Observation 2﹕ 把Relax問題放到A[1..i]，答案P[i]始終固定。

因此我們可以直接計算max{Sum[0..i] - 2 * Sum[0..P[i]] - Sum[i+1..N+1]}，當中設A[N+1] = 0，即可。