The longest subsequence with variable increasing and decreasing values

Question

Given the array, we need to find the length of the longest subsequence with variable increasing and decreasing values.

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

It may also happen that at first we have a small, then a large element.

What could be the most effective solution for this? I had a DP solution. And if we did it with brute force, how would we do it (O (n ^ 3)?)?

And this is not a homework problem.

Answer 1

You can really use the dynamic programming method here. For simplicity, suppose that we only need to find the maximum length of such a sequence seq (it is easy to find a solution for the sequence itself).

For each index, we will store 2 values:

• the maximum length of the alternating sequence ending on the element where the last step increased (for example, incr [i])
• the maximum length of the alternating sequence ending on this element, where the last step was decreasing (for example, decr [i])

also, by definition, we assume that 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] 

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

simple example in c:

 int seq[N]; // initial sequence int incr[N], decr[N]; ... // Init sequences, fill incr and decr with 1 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 the algorithm works:

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 takes the value at index 1 ('4') and checks the previous values. 7> 4, so we take the "step of transition from index 0 to index 1, the new sequence values:

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

Step 2. Accept the value 8 and repeat the previous value:

7 <8, take the increment 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, take the 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...