Pick non-adjacent towers on a ring for max coverage
A city has relay towers placed around a ring road. Each tower covers a known number of households, but two neighbouring towers interfere with each other, so they can never both be switched on. The ring is closed: the last tower is next to the first one.
The operations team does not only want the best coverage number: they need to know which towers to switch on. Implement planRingPicks(values), where values[i] is the coverage of tower i.
planRingPicks(values) // => { total, picks }
values is an array of non-negative integers. Positions i and i + 1 are neighbours, and so are the last position and position 0.picks is an array of distinct indices into values, sorted in ascending order, with no two of them neighbours on the ring.total is the sum of values at picks, and it must be the largest total any valid set of picks can reach.{ total: 0, picks: [] }.values. It can hold 10,000 towers, so the solution must run in linear time.planRingPicks([4, 1, 2, 7, 5, 3, 1]);
// => { total: 14, picks: [0, 3, 5] }
planRingPicks([6, 2, 3, 6]);
// => { total: 9, picks: [0, 2] }
// (0 and 3 would give 12, but they are neighbours on the ring)
planRingPicks([2, 1, 2, 1, 2, 1]);
// => { total: 6, picks: [0, 2, 4] }
planRingPicks([7, 7, 7]);
// => { total: 7, picks: [0] } (or [1], or [2]: any one tower)
planRingPicks([3, 9]); // => { total: 9, picks: [1] }
planRingPicks([5]); // => { total: 5, picks: [0] }
planRingPicks([]); // => { total: 0, picks: [] }