fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. void print_all(
  7.     const vector<int> seq
  8. ,   const vector<int>& len
  9. ,   int max, int pos
  10. ,   vector<int>& sofar) {
  11.     if (max == 0) {
  12.         for (int i = sofar.size()-1 ; i >= 0 ; i--)
  13.             cout << sofar[i] << " ";
  14.         cout << endl;
  15.         return;
  16.     }
  17.     int val = pos < seq.size() ? seq[pos] : -1;
  18.     for (int i = pos-1 ; i >= 0 ; i--) {
  19.         if (len[i] == max && seq[i] > val) {
  20.             sofar.push_back(seq[i]);
  21.             print_all(seq, len, max-1, i, sofar);
  22.             sofar.erase(sofar.end()-1);
  23.         }
  24.     }
  25. }
  26.  
  27. int main() {
  28.     int data[] = {5, 23, 100, 10, 4, 90, 65, 11, 18, 10};
  29.     int sz=sizeof(data)/sizeof(data[0]);
  30.     vector<int> seq(data, data+sz);
  31.     vector<int> len(seq.size());
  32.     len[0] = 1;
  33.     for (int i = 1 ; i < seq.size() ; i++)
  34.         for (int j = i-1 ; j >= 0 ; j--)
  35.             if (seq[j] > seq[i] && len[j]+1 > len[i])
  36.                 len[i] = len[j]+1;
  37.     int max = *max_element(len.begin(), len.end());
  38.     cerr << max << endl;
  39.     vector<int> sofar;
  40.     print_all(seq, len, max, seq.size(), sofar);
  41. }
Success #stdin #stdout 0.01s 2860KB
comments (?)
stdin
copy
stdout
copy 
90 65 18 10 
90 65 11 10
https://ideone.com/SP4wc
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!