Loading
Loading
A community radio station sells its evening hours to local sponsors. Each hour has a bid attached, but listeners complained about back-to-back adverts, so the station now has a rule: two neighbouring hours can never both be sponsored.
Given the bids in hour order, return the largest total the station can collect while respecting the rule. Leaving every hour unsponsored is allowed, so the answer is never below 0.
bids = [3, 8, 4, 2, 9]hour 0 (3): best = 3take it; nothing came beforehour 1 (8): best = max(3, 0 + 8) = 8dropping hour 0 for hour 1 pays morehour 2 (4): best = max(8, 3 + 4) = 8skipping hour 2 keeps 8hour 3 (2): best = max(8, 8 + 2) = 10hours 1 and 3 are not neighbourshour 4 (9): best = max(10, 8 + 9) = 17hours 1 and 4: 8 + 917Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(n) time · O(1) space
Input. Run your code to watch it work on this input, one line at a time.
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
Sponsor hours 1 and 4 for 8 + 9. No other non-neighbouring choice earns more.
Example 2
The two outer hours are not neighbours, so both can be sold: 5 + 5.