Hobanwoo and the Rhythm Game
InterviewTime limit1sMemory limit256 MB
Given note scores, choose which notes to miss so that no three consecutive notes are missed, maximizing the sum of combo times score over the notes that are hit.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Array, Greedy, Implementation
- Solved
- No attempts yet
Problem
Among the hobanwoo, a rhythm game called HOSU that launched last month is popular. HOSU awards bonus points for hitting consecutive notes, and the process works like this.
- Each note is assigned an integer score. Unlike other rhythm games, HOSU allows a note's score to be negative.
- Let the number of notes a hobanwoo hits in a row be the combo. Each time a note is hit, (current combo) × (current note's score) is added to the total score.
- If three notes in a row are missed, the score earned so far becomes 0 and no further points can be earned.
- A hobanwoo must play every note in the given order.
A hobanwoo hit every note for a full combo but did not get the maximum score. Write a program that computes the maximum score a hobanwoo can get!
Input
The first line gives the number of notes N (1 ≤ N ≤ 1,000).
The second line gives N space-separated integers a1, a2, ..., an (-10,000 ≤ a**i ≤ 10,000), where the i-th integer is the score of the i-th note.
Output
Print the maximum score a hobanwoo can get.