Overview

For each sensor \(i\), compute “itself + sum of adjacent sensors” \(M_i\), and output the maximum value. The formula differs slightly at the endpoints (\(i=1, N\)).

Analysis

The local temperature index \(M_i\) is determined only by the neighborhood of sensor \(i\) (at most 3 elements). Specifically:

• If \(i=1\): \(A_1 + A_2\)
• If \(1<i<N\): \(A_{i-1}+A_i+A_{i+1}\)
• If \(i=N\): \(A_{N-1}+A_N\)

It suffices to compute each of these and take the maximum.

The key observation here is that each \(M_i\) is computed by adding a fixed number of elements (2 or 3), so even iterating through all \(i\) in order, the total time complexity is \(O(N)\). (For example, if you were to unnecessarily recompute the sum of an entire range each time, it would become needlessly expensive, but in this problem the range we look at is always small, so a single pass suffices.)

Concrete example: When \(A=[3, -1, 4, 2]\): - \(M_1=3+(-1)=2\) - \(M_2=3+(-1)+4=6\) - \(M_3=(-1)+4+2=5\) - \(M_4=4+2=6\) The maximum is \(6\).

Algorithm

1. If \(N=2\), the answer is always \(A_1+A_2\) (the formulas for both endpoints are the same), so output it and terminate.
2. Otherwise:
   • First, set \(M_1=A_1+A_2\) as the tentative maximum ans.
   • For the middle indices \(i=2..N-1\) (or i=1..n-2 in 0-indexed), compute \(s=A_{i-1}+A_i+A_{i+1}\) and update ans=max(ans,s).
   • Finally, compute \(M_N=A_{N-1}+A_N\) and update ans as well.
3. Output ans.

Complexity

• Time complexity: \(O(N)\) (a constant number of additions and comparisons for each \(i\))
• Space complexity: \(O(N)\) (to store the input array \(A\))

Implementation Notes

• The endpoints \(M_1, M_N\) are “sums of 2 elements”, while the middle ones are “sums of 3 elements”, so case distinction is needed.

• \(N=2\) has no middle indices, so handling it as a special case is safe.

• Each \(A_i\) can be up to \(10^9\), and the sum can be up to about \(3\times 10^9\), but Python integers do not overflow.

• Since the input can be large, using fast input methods like sys.stdin.buffer.read() ensures stability.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:]))

    if n == 2:
        print(a[0] + a[1])
        return

    ans = a[0] + a[1]
    for i in range(1, n - 1):
        s = a[i - 1] + a[i] + a[i + 1]
        if s > ans:
            ans = s
    s = a[n - 2] + a[n - 1]
    if s > ans:
        ans = s

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.