Maximize watch time under adjacency constraint

You are given a sequence of videos in a feed.

• Input:
  • An integer array duration[1..n], where duration[i] is the length of video i in seconds.
  • An integer A (the user’s attention limit).
• Task:
  • Select a subset of videos in the original order (i.e., choose a subsequence).
  • Let the selected videos be i1 < i2 < ... < ik. The constraint is:
    • For every adjacent pair in the selected subsequence, duration[ij] + duration[ij+1] <= A.
  • Maximize the total watch time: sum(duration[ij]).
• Output:
  • Return the maximum achievable total watch time.

Follow-up:

• Suppose the user is allowed to rewatch the same video multiple times, and the session consists of exactly m selections (so repetitions are allowed, but the number of watched items is capped). How would you modify your approach to compute the maximum total watch time under the same adjacency constraint?

Part 1: Maximize Subsequence Watch Time Under Adjacent Duration Limit

You are given a feed of videos in a fixed order. The length of video i is duration[i]. Choose any subsequence of videos, preserving the original order. For every two adjacent videos in your chosen subsequence, the sum of their durations must be at most A. Return the maximum possible total watch time. A single selected video is always valid because it has no adjacent selected pair. Selecting no videos is allowed and has total watch time 0.

Constraints

• 0 <= len(duration) <= 200000
• 0 <= duration[i] <= 10^9
• 0 <= A <= 10^9
• The answer fits in a signed 64-bit integer.

Examples

Example 1

Input: ([], 10)
Output: 0

Explanation: There are no videos, so the best total watch time is 0.

Example 2

Input: ([12], 5)
Output: 12

Explanation: A single video has no adjacent selected pair, so it can be watched even though its duration exceeds A.

Hints

1. Let dp[i] be the maximum total watch time of a valid subsequence that must end at video i.
2. For video i, you need the best dp[j] among earlier videos j where duration[j] <= A - duration[i]. Maintain these best values by duration and query a prefix maximum.

Part 2: Maximize Exact-Length Watch Session With Rewatching

You are given a set of videos by duration. A watch session consists of exactly m selections. At each selection, you may choose any video from the list, and the same video may be chosen multiple times. The original feed order does not restrict the session. For every two consecutive selections, the sum of their durations must be at most A. Return the maximum possible total watch time for exactly m selections. If no valid session of exactly m selections exists, return -1. If m is 0, the empty session is valid and has total watch time 0.

Constraints

• 0 <= len(duration) <= 2000
• 0 <= m <= 2000
• 0 <= duration[i] <= 10^9
• 0 <= A <= 10^9
• The answer fits in a signed 64-bit integer.

Examples

Example 1

Input: ([], 10, 0)
Output: 0

Explanation: Exactly zero selections means the empty session, which is valid.

Example 2

Input: ([12, 3], 5, 1)
Output: 12

Explanation: With only one selection, there is no adjacency constraint, so choose the longest video.

Hints

1. Use dynamic programming over the session length: dp[t][d] can represent the best total for a length-t session ending with duration d.
2. For each next duration d, the previous duration must be at most A - d. Sorting distinct durations lets you use prefix maximums to speed up each transition round.