## Editorial for A Harder Contest '19 - An Alternating Problem

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: ChrisT

We can iterate through all subsequences of the original array, and calculate their alternating sum. The answer is the maximum of all possible sums which have a difference of at most between adjacent elements.

Time Complexity:

Subtask 2 was intended to reward unoptimized dynamic programming solutions.

Let represent the maximum possible alternating sum of any subsequence using only the first values in the array, and with length $$\equiv\:j\pmod{2}$$

Our base case is for all , as you can always choose an empty subsequence up to that point

$$dp[i][0] = \max\limits_{j < i} (dp[j][1] - a_i)\:iff\:|a_i-a_j|\leq M$$

$$dp[i][1] = \max\limits_{j < i} (dp[j][0] + a_i)\:iff\:|a_i-a_j|\leq M$$

On top of this, can always be at least , as you are not required to take element

Note that you must keep a parent array to find the indices used.

Time Complexity: states and transitions, thus

For the final subtask, we must optimize this dp.

Notice that the only impact of in the transition is the requirement

Thus, we can hold the best dp values for different values of in a data structure, and query the best dp value in the range

For this we will use two segment trees, one for each of , and

With this the transition is

Time Complexity: