Maximize watched duration under consecutive-sum limit
Company: TikTok
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You have a list of videos in a feed. Video *i* has duration `d[i]` (positive integer). A user has an “attention span” limit `A`.
You want to select a **subset of videos to watch** (keeping the original order, i.e., choose a subsequence of indices `i1 < i2 < ... < ik`) to **maximize total watched time**:
\[
\text{maximize } \sum_{t=1}^{k} d[i_t]
\]
subject to the constraint that **any two consecutively watched videos** do not exceed the attention span when added:
\[
d[i_t] + d[i_{t+1}] \le A \quad \text{for all } t = 1..k-1
\]
### Task
Write an algorithm/function that returns the **maximum total watched duration** achievable.
### Assumptions / clarifications
- `n = len(d)` can be large enough that brute-forcing all subsets is too slow.
- Watching 0 or 1 video is always allowed.
### Follow-up
If the user is allowed to **watch the same video multiple times**, how would you modify the approach?
- To avoid an unbounded/infinite answer, assume there is an additional limit `K` = maximum number of videos the user can watch total (including repeats). Return the maximum total watched duration under the same consecutive-sum constraint.
Quick Answer: This question evaluates algorithmic problem-solving in sequence optimization and constraint-based selection, testing competencies such as dynamic programming, subsequence selection, and handling pairwise adjacency constraints.
Part 1: Maximize Watched Duration from an Ordered Subsequence
You are given a feed of videos in a fixed order. Video i has positive integer duration d[i]. You may choose any subsequence of videos to watch, preserving the original order. The total watched duration is the sum of the chosen durations. The constraint is that every pair of consecutively watched videos must have durations whose sum is at most A. Watching zero or one video is always allowed. Return the maximum total watched duration achievable.
Constraints
- 0 <= len(d) <= 200000
- 1 <= d[i] <= 1000000000 for every valid i
- 0 <= A <= 1000000000
- The answer fits in a signed 64-bit integer.
Examples
Input: ([4, 2, 7, 3, 5], 7)
Expected Output: 11
Explanation: Choose durations [4, 2, 5]. Adjacent sums are 6 and 7, so the total is 11.
Input: ([], 10)
Expected Output: 0
Explanation: There are no videos, so watching nothing gives total 0.
Hints
- Let dp[i] be the best total watched duration for a valid subsequence that ends at video i.
- For video i with duration x, you need the maximum dp[j] among previous videos with d[j] <= A - x. Maintain prefix maximums over durations.
Part 2: Maximize Watched Duration with Replays and a Watch-Count Limit
You are given a list of videos, where video i has positive integer duration d[i]. You may now watch videos in any order, and the same video may be watched multiple times. You may watch at most K videos total, including repeated watches. The constraint is that every pair of consecutively watched videos must have durations whose sum is at most A. Watching zero videos is allowed. Return the maximum total watched duration achievable.
Constraints
- 0 <= len(d) <= 5000
- 0 <= K <= 5000
- 1 <= d[i] <= 1000000000 for every valid i
- 0 <= A <= 1000000000
- Let m = len(set(d)). Test data satisfies m * max(1, K) <= 5000000.
Examples
Input: ([4, 2, 7, 3, 5], 7, 3)
Expected Output: 12
Explanation: Watch durations [5, 2, 5]. Both adjacent sums are 7, and the total is 12.
Input: ([1, 2, 3], 4, 0)
Expected Output: 0
Explanation: K is 0, so no videos may be watched.
Hints
- Because replays are allowed, the original indices no longer matter. The useful state is the last watched duration and how many videos have been watched.
- For each sequence length and next duration x, transition from the best previous state whose last duration is at most A - x. This can be accelerated with sorted durations and prefix maximums.