Subtask 1 was intended to reward bitmask solutions.

We can iterate through all ~2^N~ 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 ~M~ between adjacent elements.

Time Complexity: ~\mathcal{O}(N\cdot 2^N)~

Subtask 2 was intended to reward unoptimized dynamic programming solutions.

Let ~dp[i][j]~ represent the maximum possible alternating sum of any subsequence using only the first ~i~ values in the array, and with length \(\equiv\:j\pmod{2}\)

Our base case is ~dp[i][0] = 0~ for all ~(0 \leq i < N)~, as you can always choose an empty subsequence up to that point

This leads to the recurrence:

\(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, ~dp[i][j]~ can always be at least ~dp[i-1][j]~, as you are not required to take element ~i~

Our answer lies in ~\max(dp[n][0],dp[n][1])~

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

Time Complexity: ~\mathcal{O}(N)~ states and ~\mathcal{O}(N)~ transitions, thus ~\mathcal{O}(N^2)~

For the final subtask, we must optimize this dp.

Notice that the only impact of ~i~ in the transition is the requirement ~|a_i-a_j|\leq M~

Thus, we can hold the best dp values for different values of ~a_i~ in a data structure, and query the best dp value in the range ~[a_i-M,a_i+M]~

For this we will use two segment trees, one for each of ~dp[x][0]~, and ~dp[x][1]~

With this the transition is ~\mathcal{O}(\log N)~

Time Complexity: ~\mathcal{O}(N \log N)~