## 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] = \max\limits_{j < i} (dp[j] - a_i)\:iff\:|a_i-a_j|\leq M$$

$$dp[i] = \max\limits_{j < i} (dp[j] + 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 Our answer lies in 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: 