打印所有可能的最长减少的子序列

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