호반우와 리듬게임
면접 대비시간 제한1초메모리 제한256 MB
각 노트의 점수가 주어질 때, 세 노트를 연속으로 놓치지 않으면서 콤보와 점수의 곱의 합이 최대가 되도록 놓칠 노트를 정하는 문제이다.
문제
호반우들 사이에서는 지난달에 나온 리듬게임 호스가 유행이다. 호스는 연속된 노트를 처리할수록 보너스 점수를 주는데, 그 방식은 다음과 같다.
- 각 노트에는 정수 점수가 매겨져 있다. 다른 리듬게임과 달리 호스에서는 점수가 음수일 수도 있다.
- 호반우가 연속으로 처리한 노트의 개수를 콤보라고 하자. 노트를 하나 칠 때마다 (누적 콤보) × (현재 노트의 점수)가 총 점수에 더해진다.
- 연속으로 노트 3개를 놓치면 지금까지 얻은 점수가 0점이 되고, 그 뒤로는 점수를 얻을 수 없다.
- 호반우는 모든 노트를 주어진 순서대로 처리해야 한다.
호반우는 모든 노트를 처리해 풀 콤보를 받았지만 최대 점수를 얻지는 못했다. 호반우가 얻을 수 있는 최대 점수를 계산하는 프로그램을 만들자!
입력
첫째 줄에 노트 개수 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에 공백으로 구분된 N개의 정수 a1, a2, ..., an (-10,000 ≤ a**i ≤ 10,000)가 주어지는데, i번째 정수는 i번째 노트의 점수를 나타낸다.
출력
호반우가 얻을 수 있는 최대 점수를 출력한다.