Christine and her friends are planning a movie marathon using her family's massive film library. They want to start with shorter movies and progress onto longer movies, but they're going to do it in a very specific way: each movie they watch must be the same length as the previous movie, or exactly one minute longer than the previous movie (counting opening and closing credits, of course). The first movie they watch can have any length. They do not want to watch any of the movies twice, even if they're not back-to-back. Popcorn will be provided.
Assume that Christine and her friends plan their movie marathon optimally. Implement the following function in the code editor to determine the maximum number of movies that the group can watch according to their rules.
Function Description
Complete the function longestMarathon in the editor.
longestMarathon has the following parameter:
int[] runtimes: an array of integers representing the collection of movie runtimes
Returns
int: the length of the largest sequence of non-repeated movies that the group can watch, such that the Nth movie in the sequence has the same runtime as, or is exactly one minute longer than, the (N-1)st movie. A return value of 0 indicates that it is not possible for the group to have a marathon at all.
Example 1:
Input: runtimes = [8, 4, 5, 7, 4]
Output: 3
Explanation:Consider a film library that consists of 5 films whose runtimes are [8, 4, 5, 7, 4].
- If the group starts with film 0 whose runtime is 8, their marathon will have length 1, as all the other movies have shorter runtimes.
- If the group starts with film 1 or film 4, each of which has a runtime of 4, they have two options to progress:
- They can watch the other film with a runtime of 4, and then film 2 whose runtime is 5, giving their marathon a length of 3
- They can immediate jump to film 2 whose runtime is 5, giving their marathon a length of 2
- If the group starts with film 2 whose runtime is 5, their marathon will have length 1, as there are no other film whose runtime is either 5 or 6
- If the group starts with film 3 whose runtime is 7, they can then watch film 0 whose runtime is 8, giving their marathon a length of 2
The function should therefore return 3.
N/A
input:
output: