c++ - 可能なすべての最長減少部分列を出力

Question

私は整数の配列A [1 ... N]を持っていました.今、私はALL LONGEST DECRIASING SUBSEQUENCEを出力したいと思います. 私はほとんどのチュートリアルを実行しましたが、すべてのチュートリアルは 1 つの 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