yukicoder 1375 Divide and Update
まず, 左・右から最大部分配列問題というのを解いていく. 最大部分配列問題とは配列に対してその連続した部分配列のうち和が最大となるものの値を求める問題のことである. 詳しくはこの記事を見ていただきたい.これはDPをしていくことで簡単に求められる. そしてその後その累積maxをとっていく. ここまでを前計算しておくことで, 各値を$ O(1)で求められる. よって計算量は$ O(N)となる.
実装例: https://yukicoder.me/submissions/613754