Alex loves movies and maintains a list of negative and/or positive integer ratings for the movies in a collection. Alex is getting ready for a film festival and wants to choose some subsequence of movies from the collection to bring such that the following conditions are satisfied:
- The collective sum of their ratings is maximal.
- Alex must go through the list in order and cannot skip more than one movie in a row. In other words, Alex cannot skip over two or more consecutive movies. For example, if ratings = [-1, -3, -2], and must include either the second number or the first and third numbers to get a maximal rating sum of -3.
Function Description
Complete the function maximizeRatings in the editor below.
maximizeRatings has the following parameter(s):
int ratings[n]: movie ratings
Returns
int: the maximum sum of the ratings of the chosen subsequence of movies
Example 1:
Input: ratings = [-3, 2, 4, -1, -2, -5]
Output: 4
Explanation:The maximal choices are [2, 4, -2] for a sum of 4.
Example 2:
Input: ratings = [9, -1, -3, 4, 5]
Output: 17
Explanation:Alex picks the bolded items in ratings = [9, -1, -3, 4, 5] to get maximum rating = 9 + 4 + 5 = 17.
- 1 ≤ n ≤ 10^5
- -1000 ≤ ratings[i] ≤ 1000, where 0 ≤ i < n
input:
output: