/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 233 点
問題文
高橋君は工場に設置された温度センサーの点検を担当しています。工場には N 個の温度センサーが一列に並んでおり、それぞれのセンサーには 1 から N までの番号が、並んでいる順に付けられています。番号が 1 だけ異なるセンサー同士が互いに隣接しています。
i 番目のセンサーが計測した温度は A_i です。
点検では、各センサーについて「局所温度指標」M_i を計算します。センサー i の局所温度指標 M_i は、センサー i 自身とそれに隣接するすべてのセンサーの計測値の合計であり、以下のように定義されます：
- 2 \leq i \leq N-1 のとき： M_i = A_{i-1} + A_i + A_{i+1}
- i = 1 のとき： M_1 = A_1 + A_2
- i = N のとき： M_N = A_{N-1} + A_N
なお、N = 2 のときは 2 番目の条件に該当するセンサーはなく、1 番目と 3 番目の条件のみが適用されます。
高橋君は、すべてのセンサーの局所温度指標の中で最大のものを報告する必要があります。
N 個のセンサーの計測値が与えられたとき、局所温度指標の最大値 \displaystyle \max_{1 \leq i \leq N} M_i を求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- -10^9 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N A_1 A_2 \ldots A_N
- 1 行目には、センサーの個数を表す整数 N が与えられる。
- 2 行目には、各センサーの計測値を表す N 個の整数 A_1, A_2, \ldots, A_N が空白区切りで与えられる。
出力
局所温度指標の最大値を 1 行に出力せよ。
入力例 1
5 3 1 4 1 5
出力例 1
10
入力例 2
2 100 -50
出力例 2
50
入力例 3
10 -5 12 8 -3 20 15 -10 7 25 18
出力例 3
50
Score : 233 pts
Problem Statement
Takahashi is in charge of inspecting temperature sensors installed in a factory. The factory has N temperature sensors arranged in a row, and each sensor is numbered from 1 to N in the order they are arranged. Sensors whose numbers differ by exactly 1 are adjacent to each other.
The temperature measured by the i-th sensor is A_i.
During the inspection, a "local temperature index" M_i is calculated for each sensor. The local temperature index M_i of sensor i is the sum of the measurements of sensor i itself and all sensors adjacent to it, defined as follows:
- When 2 \leq i \leq N-1: M_i = A_{i-1} + A_i + A_{i+1}
- When i = 1: M_1 = A_1 + A_2
- When i = N: M_N = A_{N-1} + A_N
Note that when N = 2, no sensor falls under the second condition, and only the first and third conditions apply.
Takahashi needs to report the maximum value among the local temperature indices of all sensors.
Given the measurements of N sensors, find the maximum value of the local temperature indices \displaystyle \max_{1 \leq i \leq N} M_i.
Constraints
- 2 \leq N \leq 2 \times 10^5
- -10^9 \leq A_i \leq 10^9
- All inputs are integers
Input
N A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of sensors.
- The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the measurements of each sensor.
Output
Print the maximum value of the local temperature indices on a single line.
Sample Input 1
5 3 1 4 1 5
Sample Output 1
10
Sample Input 2
2 100 -50
Sample Output 2
50
Sample Input 3
10 -5 12 8 -3 20 15 -10 7 25 18
Sample Output 3
50