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

s0=j=1MAjsi=max(si1+AM+i,j=1+iM+iAj)\begin{aligned} s_0 &= \sum_{j = 1}^{M} A_j\\ s_i &= \max\left(s_{i - 1} + A_{M + i}, \sum_{j=1+i}^{M+i} A_j\right) \end{aligned}

答えは maxisi\max_i s_i となります。式に現れる総和は累積和を使うことで O(1)O(1) で計算が可能です。