Algo : Unimodal Streak

I have this algorithmic problem to resolve, I have a vector with numbers and I must find the longest unimodal streak (that means it can increase then decrease, but not more than one time).

i.e : in the vector [4 5 8 5 9 6 3], 45863 is an unimodal streak while 458593 isn't because it's increasing to 8 then decreasing to 5 then increasing again (which is not permitted).

Using dynamic programming I managed to create 3 vectors : the first one with the length of the longest increasing streak that stops at the element x, the secon开发者_C百科d one with the length of the longest decreasing streak that starts at the element x, and the third one is the sum of the first two.

Basically if I take the maximum of the third vector it's the length of the longest unimodal streak+1 (because the element x is counted twice).

What I want to do now is to display that streak. I'm thinking of using these vectors that way : using a "for" starting at the position of the maximum and going to the beginning of the vector. The I'm going to check the value in the first vector and if that value is exactely 1 less than the previous value (the first time it will be the value of the maximum in the first vector) I will keep that value in a queue and display it later, then continue. I will then do nearly the same thing for the second part of the vector using the second vector.

I know that sounds messy and complicated but with this example it will be clearer.

I have this base vector :  
9 4 5 6 9 7 8 3 4 3

1 1 2 3 4 4 5 1 2 1 (first vector) = A
4 2 3 3 4 3 3 1 2 1 (second vector) = B
5 3 5 6 8 7 8 2 4 2 (sum of the two) = C

So the longest streak here is 7 and the peak is 9 (or 8 but thats the same thing).

So what I want to do is : The value of the peak is "4" in the first vector so I'll check the first being "3" going left, it's 6, I put it in the queue, I'm now looking for the first "2", it's 5, in the queue, and then it's 4 because it's the first with the value "1".

I will then display the queue, then the peak, then do the same thing with the second part. I will have 4 5 6 9 7 4 3. (Which is the good sequence).

My question is : Will this work every time? I have the feeling that something can screw up so I did some tests and every time it went fine. I'd like to know if there are specific base vectors that screw the thing up. If you could please tell me what you think that would be great!

Thank you for reading all this, I hope that someone can help me.

---

Looks good to me. The dynamic programming solution, if implemented correctly, is guaranteed to find the optimum because it indirectly checks all possible selections. In this case, the sequence needs to have a "center" (the point where it stops increasing and starts decreasing). That's the parameter you're brute-forcing.

One remark, though

The I'm going to check the value in the first vector and if that value is exactely 1 less than the previous value (the first time it will be the value of the maximum in the first vector) I will keep that value in a queue and display it later.

I think what you really want here is a stack, not a queue, given that the last element you'll find is the first one you want to display. That applies to the first vector.

More generally, you can use a regular array and that'll work for both vectors.

---

I think it's sound. If the maximum element of the best unimodal streak is e, then the best possible left half and right half will be found in A and B. Since the left and right sequences are totally independent, this method will always work.