#185MediumDynamic Programming· Non-Adjacent Selection on a Cycle

Circular Billboard Revenue

A ring road has `n` billboards, numbered in the order you meet them. Renting out billboard `i` earns `revenue[i]`. Two billboards that are next to each other on the road may not both be rented, because the advertisers would be adjacent competitors. Because the road is a ring, the last billboard is also next to the first. Return the largest total revenue you can earn. With a single billboard you may of course rent it.

Input format

`revenue`: an array of non-negative integers.

Output format

An integer: the maximum revenue from a set of billboards with no two adjacent on the ring.

Examples

Input: revenue = [2, 3, 2]

Output: 3

Billboards 0 and 2 are neighbours on the ring, so renting both is not allowed. The best choice is billboard 1 alone: 3.

Input: revenue = [1, 2, 3, 1]

Output: 4

Renting billboards 1 and 3 (revenue 2 + 1) conflicts with nothing and gives 3; billboards 0 and 2 earn 1 + 3 = 4, which is better.

Input: revenue = [5]

Output: 5

A single billboard has no neighbour to conflict with.

Constraints

1 <= revenue.length <= 10^5
0 <= revenue[i] <= 10^4

#dynamic-programming
#arrays
#circular-array