Overview

Given temperature data \(A_i\) from \(N\) sensors, the problem asks you to compute the “local temperature index” for each sensor — the sum of that sensor’s value and its adjacent sensors’ values — and find the maximum among them.

Analysis

The local temperature index \(M_i\) for each sensor is calculated differently depending on its position:

• Left end (\(i=1\)): Sum of itself and its right neighbor (\(A_1 + A_2\))
• Right end (\(i=N\)): Sum of itself and its left neighbor (\(A_{N-1} + A_N\))
• Otherwise (\(1 < i < N\)): Sum of itself and both neighbors (\(A_{i-1} + A_i + A_{i+1}\))

Since the value of \(N\) can be up to \(2 \times 10^5\), computing the value for each sensor sequentially results in a number of operations proportional to \(N\). Therefore, a straightforward approach using a single loop to check all \(M_i\) is sufficient to obtain the correct answer within the time limit.

As a note of caution, since temperatures \(A_i\) can take negative values, care must be taken when initializing the variable that holds the maximum value (it is safest to initialize it with the result of the first computation).

Algorithm

The implementation follows these steps:

1. Store the \(N\) input values in an array \(A\).
2. First, compute the edge cases \(M_1 = A_1 + A_2\) and \(M_N = A_{N-1} + A_N\), and set the larger of the two as the tentative maximum ans.
3. Next, use a loop (for loop) to compute \(M_i = A_{i-1} + A_i + A_{i+1}\) for sensors from \(i = 2\) to \(N-1\).
4. If the computed \(M_i\) is larger than the current ans, update ans with that value.
5. Output the final ans.

Complexity

• Time complexity: \(O(N)\)
  • Since we scan each of the \(N\) elements once, the computation finishes in time proportional to the number of sensors.
• Space complexity: \(O(N)\)
  • Memory is needed to store the \(N\) input temperature values in an array.

Implementation Notes

• Conversion to 0-indexed: Since arrays in programming languages (such as Python) are indexed starting from 0, the \(i\)-th element in the problem statement corresponds to a[i-1] in the array.

  • \(M_1\) is a[0] + a[1]
  • \(M_N\) is a[n-2] + a[n-1]
  • \(M_i\) (\(1 < i < N\)) is a[i-2] + a[i-1] + a[i]

• Efficient input: Since \(N\) can be large, in Python it is faster to read all input at once using something like sys.stdin.read().split().

  Source Code

import sys

def solve():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    a = list(map(int, data[1:]))
    
    if n < 2:
        return
    
    m1 = a[0] + a[1]
    mn = a[n-2] + a[n-1]
    ans = m1 if m1 > mn else mn
    
    for i in range(1, n - 1):
        val = a[i-1] + a[i] + a[i+1]
        if val > ans:
            ans = val
            
    print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.