Maximum Subsequence Sum with No Two Consecutive Skips

Reported in interviews at Akuna Capital

Problem statement

You are given $n$ movies in a fixed order, each with a rating that may be positive or negative. You watch a subsequence of them and score the sum of the ratings you watch. You may drop any movie, but you can never skip more than one movie in a row: between any two movies you keep -- and also before the first kept movie and after the last -- at most one movie may be dropped.

Maximize the total rating of the movies you keep.

Example: for ratings $[-3, 2, 4, -1, -2, -5]$ an optimal choice is $[2, 4, -2]$ for a total of $4$. No two consecutive movies are ever skipped, and swallowing the extra $-2$ beats stopping at $[2, 4]$, which would skip both $-2$ and $-5$ back to back.

Show hint

What is the smallest amount of information about the recent past you need to decide whether the current movie may be dropped?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems