区間/最大

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

$$\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}$$

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