Movie Marathon Max Rating
MediumDynamic Programming ยท Oracle
Given an integer array ratings, you choose which movies in a marathon to watch, in the listed order. Among any two consecutive movies, you must watch at least one. Return the largest possible sum of the ratings of the movies you watch, or 0 if ratings is empty. Ratings can be negative, and you may skip the first or the last movie.
Example 1
- Input:
- ratings = [4, -3, 5, -2, 6]
- Output:
- 15
- Explanation
- Watch 4, 5 and 6. The skipped -3 and -2 are never adjacent to each other.
Example 2
- Input:
- ratings = [-5, -1, -7, -2, -6]
- Output:
- -3
- Explanation
- Watch only the 2nd and 4th movies; every skipped movie has a watched neighbor.
Example 3
- Input:
- ratings = [-3, -8]
- Output:
- -3
Constraints
0 <= ratings.length <= 100000-10^9 <= ratings[i] <= 10^9- Ratings may repeat; the answer can reach
10^14in magnitude