I've been studying dynamic programming lately and came across a problem that is, I believe (might be wrong, though), a modification of the classic longest alternating subsequence (LAS) problem.

But instead of asking you what is the maximum length, this problem asks what is the minimum number of changes you would have to do to any V[i] element such that the whole input array becomes an alternating sequence. Changes can only be subtractions, not additions.

Example: 2 5 8 6 1 2

In this case the minimum number is 1: you can make the 8 a 4, for example.

The answer could be 0 as well if the whole sequence is already alternating.

For solving the LAS, I know we need to retain in DP[i][0] the size of the longest alternating subsequence ending at i for which the last element is greater than the previous one and in DP[i][1] the same when the last element is lesser than its previous. And we build this by iterating from 1 to i-1.

But how can I find the changes I'd need to make to turn the whole sequence into an alternating one?

  • $\begingroup$ I'm not convinced it's similar to the LAS problem precisely because we need to make the entire sequence alternating. $\endgroup$ – user111398 Nov 9 at 19:19
  • $\begingroup$ Could definitely be the case. I just noticed some kind of resemblance, but it might indeed have nothing to do with it. $\endgroup$ – theodor96 Nov 9 at 19:24
  • $\begingroup$ I'm also not sure it needs to be solved with DP; correct me if I'm wrong, but you want the final sequence to either be like $a[0]>a[1]<a[2]>\cdots$ or like $a[0]<a[1]>a[2]<\cdots$. In the first case, it should never make sense to decrease the even-indexed elements. In the second case it should never make sense to decrease the odd-indexed elements. Then our strategy might be: do the least possible to get into each of the two cases, and see which of the two yields a smaller number of decreases. $\endgroup$ – user111398 Nov 9 at 19:26
  • $\begingroup$ Hmm, not exactly. Let's take 10 20 13 14 20 15 14. 20 has index an even index, but decreasing it to anything lower than 14 makes the whole sequence alternating. $\endgroup$ – theodor96 Nov 9 at 19:49
  • $\begingroup$ That's the second case I referred to: where you want to end up with $a[0]<a[1]>a[2]<\cdots$, in which case it doesn't make sense to decrease the odd-indexed elements (so you would only possibly decrease the even indexed elements). Your suggestion indeed avoids decreasing any odd-indexed elements $\endgroup$ – user111398 Nov 9 at 20:09