c++ - 打印所有可能的最长递减子序列

Question

我有整数数组 A[1...N]。现在我想打印所有最长的递减子序列。我已经完成了大部分教程，但是所有教程都只打印一个 LDS。假设 LDS 的长度是 5，那么大多数只打印一个长度为 5 的 LDS。但我想打印所有可能的 LDS。怎么做这？？可以在 O(nlongn) 时间内完成。伪代码会更有帮助。

Answer 1

您可以随时跟踪所有最长（到目前为止）的子序列：

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

Answer 2

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);
}