Dynamic Programming Practice | Dataford Interview Questions

TikTok is selecting promotional placements from a sequence of eligible slots. Each slot has a nonnegative reward, but selecting two adjacent slots would create an unacceptable user experience, so adjacent slots cannot both be selected.

Given an integer array rewards, return the maximum total reward obtainable by selecting a subset of nonadjacent slots. You may select no slots.

Formal Specification

Input: rewards, a list of nonnegative integers, where rewards[i] is the reward for slot i.
Output: An integer representing the maximum achievable reward.
Function: Implement max_non_adjacent_reward(rewards).

Constraints

0 <= rewards.length <= 100000
0 <= rewards[i] <= 10000
Adjacent slots may not both be selected
The result fits in a standard Python integer

Function Signature

def max_non_adjacent_reward(rewards):

Your question is Dynamic Programming Practice. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem