Circular Garden Harvest

Medium

The beds of a garden are laid out in a circle: bed i neighbours beds i - 1 and i + 1, and the last bed neighbours the first one. The array beds holds the yield of each bed. Harvesting two neighbouring beds would dry out the soil between them, so that is not allowed. What is the largest total yield you can collect?

Example 1

beds=[4, 7, 3, 6] → 13

Harvesting beds 1 and 3 is best: 7 + 6 = 13. Beds 0 and 2 give only 7.

Example 2

beds=[9, 2, 1, 8] → 10

Beds 0 and 3 are neighbours around the circle, so they cannot both be taken. The best option is 9 + 1 = 10.

Example 3

beds=[5, 5, 5] → 5

Any two of three beds in a circle are neighbours, so only one can be harvested.

Constraints

1 ≤ len(beds) ≤ 100
0 ≤ beds[i] ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming

Similar problems

Fewest Jumps to the End Medium Most Profitable Streak Medium Reach the Last Cell Medium Warehouse Cart Routes Medium Cheapest Corner-to-Corner Route Medium

Input

beds=[4, 7, 3, 6]

Expected

Run checks the first 3 tests in your browser. Submit checks all 125 tests on the server, hidden ones included.