mediumDynamic Programming 1DPure DSA~22 min
Non-Adjacent Ad Revenue
An app shows ad slots down a feed, but policy forbids two ads in directly adjacent slots. Each slot has an expected revenue. Choose a subset of non-adjacent slots that maximises total expected revenue.
Problem
Given an array revenue where revenue[i] is the value of slot i, return the maximum sum obtainable by selecting elements such that no two selected elements are adjacent.
Input
An array revenue of length n (0 ≤ n ≤ 10^5), each value in [0, 10^4].
Output
A single integer — the maximum non-adjacent sum.
Constraints
- 0 ≤ n ≤ 100,000
- 0 ≤ revenue[i] ≤ 10,000
- Selected indices must be pairwise non-adjacent
Examples
Example 1
Input
revenue = [3, 2, 7, 10]
Output
13
Pick slots 0 and 3 (3 + 10 = 13). They are non-adjacent and beat alternatives like slots 0 and 2 (3 + 7 = 10) or slot 3 with slot 1 (10 + 2 = 12).
Example 2
Input
revenue = [5, 1, 1, 5]
Output
10
Pick the two ends (5 + 5 = 10); they are not adjacent.