Enunț

Se consideră un şir a cu n numere naturale distincte: a1, a2,..., an.

Exemplu

varf.in

4
2 1 4 3

varf.out

2 4 3 
1 4 3 

Explicație

Se pot construi doar două subșiruri vârf: (2,4,3) și (1,4,3).

#include <bits/stdc++.h>


using namespace std;

ifstream cin ("varf.in");
ofstream cout ("varf.out");

int a[12], n, rez[12], cnt;
vector< vector<int> > nextmin, nextmax;

void afis(int n)
{
    cnt ++;
    for (int i = 1; i <= n; ++ i)
        cout << rez[i] << ' ';
    cout << '\n';
}
void backt(int i, int ind, int varf)
{
    if (ind == 0)
    {
        for (int i = 1; i <= n; i ++)
        {
            rez[ind + 1] = a[i];
            backt(i, ind + 1, varf);
        }
    }
    else if (varf == 0)
    {
        if (ind != 1)
        {
            for (int j = i + 1; j <= n; j ++)
            {
                rez[ind + 1] = a[j];
                if (a[i] < a[j])backt(j, ind + 1, 0);
                else backt(j, ind + 1, 1);
            }
        }
        else
        {
            for (int j = 0; j < nextmax[i].size(); j ++)
            {
                rez[ind + 1] = a[nextmax[i][j]];
                backt(nextmax[i][j], ind + 1, varf);
            }
        }
    }
    else
    {
        afis(ind);
        for (int j = 0; j < nextmin[i].size(); j ++)
        {
            rez[ind + 1] = a[nextmin[i][j]];
            backt(nextmin[i][j], ind + 1, varf);
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];

    nextmin = nextmax = vector< vector<int> >(n + 1);

    for (int i = 1; i <= n; i ++)
        for (int j = i + 1; j <= n; j ++)
            if (a[i] < a[j])nextmax[i].push_back(j);
            else if (a[i] > a[j])nextmin[i].push_back(j);

    backt(1, 0, 0);
    if (cnt == 0)cout << '0';
    return 0;
}