All problems

Tour Without Burnout

Medium · dynamic programming

A band is offered one gig every day of a tour, and pay[i] is what the gig on day i pays. They may play any days they like, but the band is not allowed to play on three days in a row: playing two days running is fine, a third straight day is not. Days they skip pay nothing.

Return the most money the band can earn over the whole tour. Playing a gig that pays 0 is allowed and changes nothing.

Examples

Example 1

Input: pay = [4, 5, 6, 3]

Output: 13

Play days 0, 2 and 3: 4 + 6 + 3 = 13. Playing days 1, 2 and 3 would pay more but is three days in a row.

Example 2

Input: pay = [10, 10, 10]

Output: 20

Any two of the three days; all three is not allowed.

Example 3

Input: pay = [7]

Output: 7

Constraints