#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, 23, 100, 10, 4, 90, 65, 11, 18, 10};
int sz=sizeof(data)/sizeof(data[0]);
vector<int> seq(data, data+sz);
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);
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdm9pZCBwcmludF9hbGwoCiAgICBjb25zdCB2ZWN0b3I8aW50PiBzZXEKLCAgIGNvbnN0IHZlY3RvcjxpbnQ+JiBsZW4KLCAgIGludCBtYXgsIGludCBwb3MKLCAgIHZlY3RvcjxpbnQ+JiBzb2ZhcikgewogICAgaWYgKG1heCA9PSAwKSB7CiAgICAgICAgZm9yIChpbnQgaSA9IHNvZmFyLnNpemUoKS0xIDsgaSA+PSAwIDsgaS0tKQogICAgICAgICAgICBjb3V0IDw8IHNvZmFyW2ldIDw8ICIgIjsKICAgICAgICBjb3V0IDw8IGVuZGw7CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgaW50IHZhbCA9IHBvcyA8IHNlcS5zaXplKCkgPyBzZXFbcG9zXSA6IC0xOwogICAgZm9yIChpbnQgaSA9IHBvcy0xIDsgaSA+PSAwIDsgaS0tKSB7CiAgICAgICAgaWYgKGxlbltpXSA9PSBtYXggJiYgc2VxW2ldID4gdmFsKSB7CiAgICAgICAgICAgIHNvZmFyLnB1c2hfYmFjayhzZXFbaV0pOwogICAgICAgICAgICBwcmludF9hbGwoc2VxLCBsZW4sIG1heC0xLCBpLCBzb2Zhcik7CiAgICAgICAgICAgIHNvZmFyLmVyYXNlKHNvZmFyLmVuZCgpLTEpOwogICAgICAgIH0KICAgIH0KfQoKaW50IG1haW4oKSB7CiAgICBpbnQgZGF0YVtdID0gezUsIDIzLCAxMDAsIDEwLCA0LCA5MCwgNjUsIDExLCAxOCwgMTB9OwogICAgaW50IHN6PXNpemVvZihkYXRhKS9zaXplb2YoZGF0YVswXSk7CiAgICB2ZWN0b3I8aW50PiBzZXEoZGF0YSwgZGF0YStzeik7CiAgICB2ZWN0b3I8aW50PiBsZW4oc2VxLnNpemUoKSk7CiAgICBmb3IgKGludCBpID0gMCA7IGkgPCBzZXEuc2l6ZSgpIDsgaSsrKSB7CiAgICAgICAgbGVuW2ldID0gMTsKICAgICAgICBmb3IgKGludCBqID0gaS0xIDsgaiA+PSAwIDsgai0tKQogICAgICAgICAgICBpZiAoc2VxW2pdID4gc2VxW2ldICYmIGxlbltqXSsxID4gbGVuW2ldKQogICAgICAgICAgICAgICAgbGVuW2ldID0gbGVuW2pdKzE7CiAgICB9CiAgICBpbnQgbWF4ID0gKm1heF9lbGVtZW50KGxlbi5iZWdpbigpLCBsZW4uZW5kKCkpOwogICAgY2VyciA8PCBtYXggPDwgZW5kbDsKICAgIHZlY3RvcjxpbnQ+IHNvZmFyOwogICAgcHJpbnRfYWxsKHNlcSwgbGVuLCBtYXgsIHNlcS5zaXplKCksIHNvZmFyKTsKfQ==