Plaza Ring Sponsor

Medium1-D Dynamic Programming

Problem

This year the festival stalls stand in a ring around a plaza, so the first stall and the last stall are neighbours. Sponsoring stall i earns values[i] points, and you may not sponsor two neighbouring stalls.

Return the maximum total points you can earn.

Example 1

Input:
values = [2, 3, 2]
Output:
3

Stalls 0 and 2 are neighbours in the ring, so the best is stall 1 alone.

Example 2

Input:
values = [1, 2, 3, 1]
Output:
4

Stalls 0 and 2: 1 + 3.

Constraints

  • 1 ≤ values.length ≤ 10^4
  • 0 ≤ values[i] ≤ 1000

Hint

Show the first hint

The ring only adds one constraint compared to a line: stalls 0 and n - 1 cannot both be chosen.

Walkthrough

How to approach it

01Clarify before coding

  • With a single stall, is it its own neighbour? No: one stall can be sponsored, so return values[0].
  • With two stalls, they are neighbours both ways: pick the larger.
  • Values are non-negative? Yes.

02Brute force

Enumerate every subset, reject those with two ring-neighbours, keep the best sum.

Cost: O(2ⁿ·n): hopeless beyond about 25 stalls.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.