Overview

This problem asks you to find the maximum sum of a “contiguous interval of length \(M\)” from an array arranged in a circular fashion.
By using a sliding window that shifts the starting position and updates the sum, we can efficiently examine all candidates while naturally handling the circular structure.

Key Observations

There are two important observations:

1. The visible gondolas are “\(M\) consecutive elements on a circular array.”
   → If we let the starting position be \(0, 1, 2, \dots, N-1\), there are exactly \(N\) candidate intervals.

2. Adjacent starting positions share almost the same interval.
   For example, when moving the starting position from \(s-1\) to \(s\):

   • One element leaves from the left end.
   • One element enters from the right end.
     Therefore, we don’t need to re-sum all \(M\) elements for each interval.

---

A naive approach would compute the sum of length \(M\) for each starting position, resulting in \(O(NM)\).
Given the constraint \(N \le 5 \times 10^5\), this can become extremely large in the worst case and will result in TLE.

Instead, we compute only the initial interval sum in \(O(M)\), and then update as follows:

[ \text{current} \leftarrow \text{current} - A[\text{out}] + A[\text{in}] ]

This takes \(O(1)\) per starting position, and \(O(N)\) overall.

Since the index of the “entering element” wraps around the end of the circular array, we handle it correctly with:

[ \text{in_idx} = (s + M - 1) \bmod N ]

Algorithm

1. Read the input.
2. Compute the sum of the initial interval (starting position \(0\), i.e., \(A[0] \sim A[M-1]\)) as current. Set best = current.
3. Try each starting position from \(s=1\) to \(N-1\) in order:
   • Index of the leaving element: out_idx = s - 1
   • Index of the entering element: in_idx = (s + M - 1) % N
   • current += A[in_idx] - A[out_idx]
   • best = max(best, current)
4. Output best.

With this procedure, we evaluate every interval of length \(M\) on the circular array exactly once without missing any.

Complexity

• Time complexity: \(O(N)\)
  (Initial sum computation \(O(M)\) + loop \(O(N)\), linear in total)
• Space complexity: \(O(1)\)
  (Additional memory excluding the input array)

Implementation Notes

• To correctly handle cases with negative values, initialize with best = current (do not initialize with 0).

• The circular structure is handled by wrapping indices with % N.

• The case \(M = N\) also works correctly as-is (every starting position yields the same total sum).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    # 初期区間 [0, M-1]
    current = sum(A[:M])
    best = current

    # 円環対応のため、開始位置を 1 から N-1 まで試す
    for s in range(1, N):
        out_idx = s - 1
        in_idx = (s + M - 1) % N
        current += A[in_idx] - A[out_idx]
        if current > best:
            best = current

    print(best)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.