Drucken Sie alle möglichen Längste abnehmende Untersequenz

Question

Ich hatte Array von ganzen Zahlen A [1 ... N]. Jetzt möchte ich ALLE LANGZEITIGES ABSTIEG SUBSEQUENCE drucken. Ich habe das meiste des Tutorials durchgegangen, aber alle Tutorials drucken nur ein LDS. Nehmen Sie an, die Länge von LDS ist 5, dann drucken die meisten nur ein LDS der Länge 5. Aber ich möchte alle möglichen LDS.Wie zu drucken tun dies? Kann es in O (nlongn) Zeit getan werden. Pseudocode wird hilfreicher sein.

Answer 1

Es ist einfacher, die Idee zu verstehen, wenn Sie un-Optimierer der Algorithmus von Ihrem Tutorial und ein verwenden einfacherer N^2 Algorithmus, der linear zurück sucht, anstatt in der Karte nachzuschlagen. Ändern Sie dann den Code, der die Sequenz druckt, um nach dem vorherigen Element rückwärts zu suchen, anstatt es in vector<int> pre zu speichern. Dann könnten Sie alle Sequenzen mit einem einfachen rekursiven Backtracker drucken:

#include <iostream> 
#include <vector> 
#include <algorithm> 
using namespace std; 

void print_all(
    const vector<int> seq 
, const vector<int>& len 
, int max, int pos 
, vector<int>& sofar) { 
    if (max == 0) { 
     for (int i = sofar.size()-1 ; i >= 0 ; i--) 
      cout << sofar[i] << " "; 
     cout << endl; 
     return; 
    } 
    int val = pos < seq.size() ? seq[pos] : -1; 
    for (int i = pos-1 ; i >= 0 ; i--) { 
     if (len[i] == max && seq[i] > val) { 
      sofar.push_back(seq[i]); 
      print_all(seq, len, max-1, i, sofar); 
      sofar.erase(sofar.end()-1); 
     } 
    } 
} 

int main() { 
    int data[] = {5, 30, 2, 17, 92, 11, 7, 10, 2, 1}; 
    vector<int> seq(data, data+10); 
    vector<int> len(seq.size()); 
    for (int i = 0 ; i < seq.size() ; i++) { 
     len[i] = 1; 
     for (int j = i-1 ; j >= 0 ; j--) 
      if (seq[j] > seq[i] && len[j]+1 > len[i]) 
       len[i] = len[j]+1; 
    } 
    int max = *max_element(len.begin(), len.end()); 
    cerr << max << endl; 
    vector<int> sofar; 
    print_all(seq, len, max, seq.size(), sofar); 
} 

Answer 2

können Sie behalten den Überblick über Ihre längste (bisher) Teilfolgen, wie Sie gehen:

// If you have only one element, that is the longest descending subsequence 
// Otherwise store first element as previous 

if: current element is less than (or equal to) previous 
    // decreasing 
    increase current subsequence length 
    add element to current subsequence 
else: 
    // increasing 
    set current subsequence length to 0 
    empty current subsequence 

if: current subsequence is longer than current maximum 
    invalidate all current max subsequences 
    set current maximum subsequence length to current subsequence length 
    add current subsequence to set of longest subsequences 
else if: current subsequence is same size as current maximum 
    add current subsequence to set of longest subsequences