Maximize Movie Ratings Without Skipping Two in a Row

## Problem An array contains positive or negative movie ratings in viewing order. Choose a subsequence with maximum total rating subject to one rule: you may not skip two consecutive movies. Return the maximum attainable sum. ### Function Contract Implement `maxRatingSum(ratings)`. ### Constraints & Assumptions - `1 <= len(ratings) <= 1,000,000`. - `-10^9 <= ratings[i] <= 10^9`. - At least one movie must be selected. - Skipping the first or last movie is allowed, but no adjacent pair of positions may both be skipped. - Use a wide integer type for the result. ### Clarifying Questions to Ask - Must selected movies be contiguous? No; they form a subsequence. - Can every rating be negative? Yes. - Does “cannot skip more than one consecutive movie” mean each adjacent pair contains a selected movie? Yes. - Is selecting no movies allowed? No. ```hint Track the previous choice At position `i`, the best state depends on whether movie `i` is selected or skipped; a skip is legal only after a selection. ``` ```hint Preserve negative states Do not initialize an impossible state to zero if that would accidentally allow an empty selection to beat every negative valid choice. ``` ### Examples ```text ratings = [5, -2, 4] output = 9 ratings = [-5, -1, -4] output = -1 ``` In the second example, selecting only the middle movie skips one movie on each side but never skips two adjacent positions. ### Evaluation Focus - Applies the rule to leading, internal, and trailing skips. - Handles all-negative input without choosing an invalid empty subsequence. - Uses constant auxiliary state rather than a full table. - Runs in `O(n)` time. ### Extensions to Discuss 1. How would you reconstruct the selected indices? 2. What changes if up to `k` consecutive movies may be skipped? 3. How would a requirement to select the first and last movie simplify the states?