この問題は、 Kadane's Algorithm の変形を使うことで解くことができます。

答えは となります。式に現れる総和は累積和を使うことで で計算が可能です。