Festival Stall Sponsor
Easy1-D Dynamic ProgrammingFree
Problem
A street festival has a single row of stalls. Sponsoring stall i brings you values[i] points of publicity, but the organisers forbid sponsoring two stalls that stand next to each other.
Return the maximum total publicity you can collect. Sponsoring no stall at all is allowed.
Example 1
- Input:
- values = [2, 7, 9, 3, 1]
- Output:
- 12
Sponsor stalls 0, 2 and 4: 2 + 9 + 1 = 12.
Example 2
- Input:
- values = [5, 1, 1, 5]
- Output:
- 10
Stalls 0 and 3 are not neighbours: 5 + 5.
Constraints
- 1 ≤ values.length ≤ 10^4
- 0 ≤ values[i] ≤ 1000
Hint
Show the first hint
Look at the last stall only: either you sponsor it or you do not.
Walkthrough
How to approach it
01Clarify before coding
- Can values be negative? No, 0 to 1000, so you never lose by adding a stall when allowed.
- Is the row circular, so the first and last stalls are neighbours? No, it is a straight line.
- May I sponsor nothing? Yes, which only matters when every value is 0.
02Brute force
Enumerate every subset of stalls with no two adjacent and keep the best sum, or recurse 'take i and jump to i + 2' versus 'skip i and go to i + 1'.
Cost: The number of valid subsets grows like Fibonacci, O(1.62ⁿ): impossible for 10^4 stalls. Memoising the recursion on i fixes it at O(n) time and O(n) space.
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.