A beekeeper inspects a straight row of n hives, left to right. Hive i holds h[i] units of honey. To avoid agitating neighbouring colonies, the keeper may not harvest two hives that sit directly next to each other in the row. Harvesting no hives at all is allowed (yielding 0).
Determine the maximum total honey the keeper can collect.
Line 1: the integer n.
Line 2: n space-separated non-negative integers h[0] h[1] ... h[n-1].
A single integer: the maximum total honey collectable with no two chosen hives adjacent.
Example 1
Input
5 2 7 9 3 1
Expected
12
Explanation
Harvest hives 0, 2, and 4 (2 + 9 + 1 = 12). No two are adjacent, and no allowed choice beats 12.
Example 2
Input
1 5
Expected
5
Explanation
With a single hive the best choice is to harvest it for 5.
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 →