Cómo salida de todas las secuencias más largo decrecientes

Question

Supongamos que tengo una matriz de enteros que tienen longitud $ N $. ¿Cómo puede la salida más larga que toda disminución de secuencias? (Una subsecuencia se compone de elementos de la matriz que no tienen que ser consecustive, por ejemplo $ (3,2,1) $ es una subsecuencia decreciente de $ (7,3,5,2,0,1) $.) yo sé cómo calcular la longitud de las secuencias más largas decrecientes, pero no saben cómo informar de todas las secuencias más largas decrecientes.

Pseudocódigo será útil.

Answer 1

Consider the following sequence as your input:

$$n,n-2,n-1,n-3,n-5,n-4,n-6,n-8,n-7,n-9, .... , n-3 \cdot k - 2, n-3 \cdot k - 1, n-3 \cdot k - 3, ....$$

for simplicity assume $n = 3\cdot t + 1$, longest decreasing subsequence length will be $t$ and number of decreasing subsequence of length $t$ is $2^t$.

So number of avilable solutions is $\Theta(2^{n/3})$. But why is so, simply model it with DAG, take care there is an edge from $a$ → $b$, if $a > b$ and $b$ is after $a$ in original sequence.

So because output size can be exponential, your best choice is creating DAG, and finding all longest paths in DAG or any other ways which enumerates all acceptable ways.

Answer 2

-a recursive helper function

    list form_longest_sublist_from(list array,list buffer,from) 
            add array[from] to buffer

            list ret as copy of buffer
            from i = from - 1 to -1 step -1
                   if last buffer > array[i] 
                   list sbuffer
                   sbuffer = form_longest_sublist_from(array,buffer,i);
                   if length sbuffer > length ret
                      ret = sbuffer;
                   endif
                endif
            endfor
            return ret;
    endfunc

• The algorithm to use the function

  list of lists arrayoflongestlist
      list buffer;
      from i = length array - 1 to -1 step -1
          clear buffer
          add array[i] to buffer
          from x = i - 1 to -1 step -1
              if(array[x] < last buffer
                  list sbuffer;
                  sbuffer = form_longest_sublist_from(array,buffer,x);
                  if length sbuffer > length buffer)
                      buffer = sbuffer;
                              endif
              endif
          endfor
              if length arrayoflongestlist > 0
                     if length (last arrayoflongestlist) < length buffer
                              clear arrayoflongestlist
                              add buffer to arrayoflongestlist
                     endif
                     else if length (last arrayoflongestlist) == length buffer
                  add buffer to arrayoflongestlist
              endif
  
                     if length (last arrayoflongestlist) > i)
                  break;
          else
              add buffer to arrayoflongestlist
          endif
      endfor
  

I basically redid the whole algorithm to be a fit for the problem.

The basic idea is to start from each possible point (each element) in the array and form all possible decreasing sublists by going thorugh the rest of the array and see which elements are smaller and use those elements to start a recursion which does the same mentioned before starting from that point and then filtering the recursions for the longest list given back.

My possible worst/bestcase scenarios mentioned before are of cause not correct considering this algorithm.

Answer 3

For every decreasing sequence, store the initial positions in another array.

for( i = 0; i < n-1; i++ ) {
    if ( a[i] > a[i+1] ) {
        temp[j++] = i;
        while( a[i] > a[i+1] ) {
            i++;
        }
        temp[j++] = i;
    }
}

Now the array temp will contain initial and final positions of all the decreasing sequences consecutively. Then print them