打印所有可能的最長減少的子序列

Question

我有一個整數數組A [1 ... N]。現在我想打印所有最長的減少子數。我經歷了大部分的教程，但所有的教程只打印一個LDS。假設LDS的長度是5，那麼大多數教程只打印一個長度爲5的LDS。 但我想打印所有可能的LDS。如何這樣做嗎？可以在O（nlongn）時間內完成。僞代碼會更有幫助。

Answer 1

這是比較容易理解的想法，如果你未優化從教程的算法，並使用更簡單的N^2算法，它可以線性回溯而不是在地圖上查找。然後修改打印序列的代碼以向後搜索先前的元素，而不是將其存儲在vector<int> pre中。然後你可以用簡單的遞歸回溯器打印所有序列：

#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

您可以跟蹤你所有的時間最長（迄今爲止）的子序列，你走：

// 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