스위치

면접 대비

시간 제한1초메모리 제한1024 MB

요약

서로 겹치지 않는 연속된 3초 구간을 골라 점수를 두 배로 할 때 얻을 수 있는 최대 총점을 구합니다.

난이도: 보통10점 중 4점
유형: 동적 계획법, 배열
정답자: 아직 제출이 없습니다

문제

$i$ 초에 $A_i$ 점을 얻는 게임이 있다. 이 게임은 $N$ 초 동안 진행된다. 추가 점수를 얻기 위해 $T$ 초에 스위치를 누를 수 있다. 스위치를 누르면 $T$ 초, $T+1$ 초, $T+2$ 초에 얻는 점수가 2배가 된다. $T$ 초에 스위치를 누른 뒤에는 $T+3$ 초부터 다시 스위치를 누를 수 있다.

게임이 진행되는 동안 스위치를 적절히 눌러 얻을 수 있는 점수의 최댓값을 구하라.

입력

첫째 줄에 점수를 얻는 횟수 $N$ 이 주어진다. $\left( 3 \leq N \leq 200\,000 \right)$

둘째 줄에 $i$ 초에 얻는 점수를 나타내는 정수 $A_i$ 가 공백으로 구분되어 주어진다. $\left( 1 \leq i \leq N;\ |A_i| \leq 1000 \right)$

출력

얻을 수 있는 점수의 최댓값을 출력한다.

예제4

예제 1
입력
```
3
-2 0 1
```
예상 출력
```
0
```
예제 2
입력
```
4
1 2 3 4
```
예상 출력
```
20
```
예제 3
입력
```
5
-1 -2 -3 -4 -5
```
예상 출력
```
-15
```
예제 4
입력
```
9
-2 10 2 -7 9 1 -2 -3 4
```
예상 출력
```
34
```