Databases
StackOverflow2013
Postsdbo
POAlgo : Unimodal Streak
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POAlgo : Unimodal Streak
    primarykey
    data
    text
    <p>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).</p> <p>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).</p> <p>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 second 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.</p> <p>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).</p> <p>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.</p> <p>I know that sounds messy and complicated but with this example it will be clearer.</p> <pre><code>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 </code></pre> <p>So the longest streak here is 7 and the peak is 9 (or 8 but thats the same thing).</p> <p>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 <strong>6</strong>, I put it in the queue, I'm now looking for the first "2", it's <strong>5</strong>, in the queue, and then it's <strong>4</strong> because it's the first with the value "1". </p> <p>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).</p> <p>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!</p> <p>Thank you for reading all this, I hope that someone can help me.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USSword22
    1. USSword22
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POAlgo : Unimodal Streak
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POAlgo : Unimodal Streak
      1. USSummer_More_More_Tea
      1. VTFavorite
    1. COWhy is the peak 4 and not 5? Are you taking the maximum of the base vector or the maximum of A?
      singulars
      1. POAlgo : Unimodal Streak
      1. USIVlad
    2. COThe peak is 9, which has the value 4 in A. The only maximum I track is the maximum of C which give me the position of the peak.
      singulars
      1. POAlgo : Unimodal Streak
      1. USSword22
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload