Longest subsequence with alternating increasing and decreasing values

Question

Given an array , we need to find the length of longest sub-sequence with alternating increasing and decreasing values.

For example , if the array is , 7 4 8 9 3 5 2 1 then the L = 6 for 7,4,8,3,5,2 or 7,4,9,3,5,1 , etc.

It could also be the case that first we have small then big element.

What could be the most efficient solution for this ? I had a DP solution in mind. And if we were to do it using brute force how would we do it (O(n^3) ?) ?

And it's not a homework problem.

Answer 1

You indeed can use dynamic programming approach here. For sake of simplicity , assume we need to find only the maximal length of such sequence seq (it will be easy to tweak solution to find the sequence itself).

For each index we will store 2 values:

• maximal length of alternating sequence ending at that element where last step was increasing (say, incr[i])
• maximal length of alternating sequence ending at that element where last step was decreasing (say, decr[i])

also by definition we assume incr[0] = decr[0] = 1

then each incr[i] can be found recursively:

incr[i] = max(decr[j])+1, where j < i and seq[j] < seq[i]
decr[i] = max(incr[j])+1, where j < i and seq[j] > seq[i]

Required length of the sequence will be the maximum value in both arrays, complexity of this approach is O(N*N) and it requires 2N of extra memory (where N is the length of initial sequence)

simple example in c:

int seq[N]; // initial sequence
int incr[N], decr[N];

... // Init sequences, fill incr and decr with 1's as initial values

for (int i = 1; i < N; ++i){
    for (int j = 0; j < i; ++j){
         if (seq[j] < seq[i]) 
         {
             // handle "increasing" step - need to check previous "decreasing" value
             if (decr[j]+1 > incr[i])  incr[i] = decr[j] + 1;
         }
         if (seq[j] > seq[i]) 
         {
             if (incr[j]+1 > decr[i])  decr[i] = incr[j] + 1;
         }
    }
}

... // Now all arrays are filled, iterate over them and find maximum value

How algorithm will work:

step 0 (initial values):

seq  = 7   4 8 9 3 5 2 1
incr = 1   1 1 1 1 1 1 1
decr = 1   1 1 1 1 1 1 1

step 1 take value at index 1 ('4') and check previous values. 7 > 4 so we make "decreasing step from index 0 to index 1, new sequence values:

incr = 1 1   1 1 1 1 1 1
decr = 1 2   1 1 1 1 1 1

step 2. take value 8 and iterate over previous value:

7 < 8, make increasing step: incr[2] = MAX(incr[2], decr[0]+1):

incr = 1 1 2   1 1 1 1 1
decr = 1 2 1   1 1 1 1 1

4 < 8, make increasing step: incr[2] = MAX(incr[2], decr[1]+1):

incr = 1 1 3   1 1 1 1 1
decr = 1 2 1   1 1 1 1 1

etc...