Problem Brief

Max Likes

You are a TT content creator with predictions about which trends will be popular over the next n days. These trends are represented by an array prediction, where the trend that will be popular on the i-th day is given by prediction[i].

Before the trends gain popularity, you need to select a set of trends to focus on. For each trend x that you choose, you will earn x likes each time that trend appears in the prediction array. However,to maintain diversity in your content, if you choose the x-th trend, you cannot choose the (x-1)-th or (x+1)-th trends, as they are considered too similar.

Your objective is to maximize the number of likes you can earn by carefully selecting which trends to focus on. Since the number of like can be large, return your answer modulo 10^9 + 7.

1Example 1

Input

prediction = [1, 3, 2]

Output

Explanation

Choose trends 1 and 3. You will get 1 like on the first day and 3 likes on the second day. The total number of likes is 4.

Draft autosaves locally

public int maxLikes(int[] prediction) {
  // write your code here
}

Input

prediction

[1, 3, 2]

Output