You are given n values in a row. You may select any subset of them (possibly none), subject to one rule: you may never select three CONSECUTIVE values (selecting two in a row is fine, but not three). Maximize the total sum of the selected values (values may be negative).
Line 1: an integer n.
Line 2: n space-separated integers v_1 ... v_n (empty if n = 0).
A single integer: the maximum achievable sum (selecting nothing, for a total of 0, is always allowed).
Example 1
Input
3 3 4 5
Expected
9
Explanation
Taking all three values would be 3 consecutive picks, which is forbidden; the best allowed choice is the last two, 4 + 5 = 9.
Example 2
Input
3 -5 -5 -5
Expected
0
Explanation
All values are negative, so selecting nothing gives the best total, 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →