Overview

This problem involves a row of temperature sensors, where we need to calculate the “sum of each sensor’s measurement and its adjacent sensors’ measurements” and find the maximum value.

Analysis

Understanding the Problem

First, let’s organize how to calculate the local temperature index: - Edge sensors (\(i = 1\) or \(i = N\)): Since they have only one neighbor, the sum is: self + one neighbor = sum of 2 values - Middle sensors (\(1 < i < N\)): Since they have neighbors on both sides, the sum is: left neighbor + self + right neighbor = sum of 3 values

Verification with a Concrete Example

For example, when \(N = 5\) and \(A = [3, 1, 4, 1, 5]\): - \(M_1 = A_1 + A_2 = 3 + 1 = 4\) - \(M_2 = A_1 + A_2 + A_3 = 3 + 1 + 4 = 8\) - \(M_3 = A_2 + A_3 + A_4 = 1 + 4 + 1 = 6\) - \(M_4 = A_3 + A_4 + A_5 = 4 + 1 + 5 = 10\) - \(M_5 = A_4 + A_5 = 1 + 5 = 6\)

Therefore, the maximum value is \(10\).

Approach Considerations

This problem can be solved by simply calculating the local temperature index for each sensor and finding the maximum value.

• Naive approach: Calculate according to the definition for each sensor → \(O(N)\)
• This is sufficiently fast, so implementing it directly will get AC.

No special optimization or algorithm is required, and \(O(N)\) is sufficient for the constraint \(N \leq 2 \times 10^5\).

Algorithm

1. Read the number of sensors \(N\) and the measurement array \(A\)
2. Initialize a variable max_m to hold the maximum value with a sufficiently small value (negative infinity)
3. For \(i = 0\) to \(N-1\), do the following:
   • If \(i = 0\) (first element): \(M_i = A_0 + A_1\)
   • If \(i = N-1\) (last element): \(M_i = A_{N-2} + A_{N-1}\)
   • Otherwise: \(M_i = A_{i-1} + A_i + A_{i+1}\)
   • Update max_m: max_m = max(max_m, M_i)
4. Output max_m

Complexity

• Time complexity: \(O(N)\)
  • The local temperature index is calculated in constant time for each sensor
  • The loop runs \(N\) times
• Space complexity: \(O(N)\)
  • For storing the input array \(A\)

Implementation Notes

1. Be careful with array indices: In the problem statement, sensor numbers start from \(1\), but in Python, array indices start from \(0\). The code processes using \(0\)-indexed arrays.

2. Setting the initial value: Since measurements \(A_i\) can be negative (down to \(-10^9\)), the initial value for the maximum should be float('-inf') (negative infinity). If initialized with \(0\), the correct answer won’t be obtained when all local temperature indices are negative.

3. Checking for overflow: Since the local temperature index is the sum of at most 3 values, it can be at most around \(3 \times 10^9\). In Python, there’s no need to worry about integer overflow, but in other languages, you may need to use a 64-bit integer type.

   Source Code

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    max_m = float('-inf')
    
    for i in range(N):
        if i == 0:
            m = A[0] + A[1]
        elif i == N - 1:
            m = A[N - 2] + A[N - 1]
        else:
            m = A[i - 1] + A[i] + A[i + 1]
        
        max_m = max(max_m, m)
    
    print(max_m)

solve()

---

This editorial was generated by claude4.5opus.