概要

各センサー \(i\) について「自分＋隣接センサーの和」\(M_i\) を求め、その最大値を出力する問題です。端（\(i=1, N\)）だけ式が少し異なります。

考察

局所温度指標 \(M_i\) は、センサー \(i\) の近傍（最大3要素）だけで決まります。つまり、

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

をそれぞれ計算し、その最大を取れば十分です。

ここで重要なのは、各 \(M_i\) が「固定個数（2または3個）の足し算」で求まるため、全ての \(i\) を順に見ても計算量は \(O(N)\) で済む点です。
（例えば「全区間の和を毎回作る」ような無駄な計算をすると不要に重くなりますが、この問題ではそもそも見る範囲が常に小さいので、1回の走査で終わります。）

具体例：\(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\) 最大は \(6\) です。

アルゴリズム

1. \(N=2\) の場合、答えは必ず \(A_1+A_2\)（両端の式が同じ）なのでそれを出力して終了。
2. それ以外では、
   • まず \(M_1=A_1+A_2\) を暫定最大値 ans にする。
   • 中央 \(i=2..N-1\)（0-indexなら i=1..n-2）について
     \(s=A_{i-1}+A_i+A_{i+1}\) を計算し、ans=max(ans,s) を更新する。
   • 最後に \(M_N=A_{N-1}+A_N\) も計算して ans を更新する。
3. ans を出力する。

計算量

• 時間計算量: \(O(N)\)（各 \(i\) について定数回の加算と比較）
• 空間計算量: \(O(N)\)（入力配列 \(A\) を保持）

実装のポイント

• 端の \(M_1, M_N\) は「2要素の和」、中央は「3要素の和」なので場合分けする。

• \(N=2\) は中央が存在しないため特別扱いすると安全。

• \(A_i\) は最大で \(10^9\)、和は最大で \(3\times 10^9\) 程度になり得るが、Python の整数ならオーバーフローしない。

• 入力が大きいので sys.stdin.buffer.read() のような高速入力を使うと安定します。

  ソースコード

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()

この解説は gpt-5.2-high によって生成されました。