Cod sursa(job #1725412)

Utilizator BossuSmekeruStapanulocu1 BossuSmekeru Data 5 iulie 2016 17:36:18
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>

using namespace std;

int main()
{
    ifstream cin ("scmax.in");
    ofstream cout ("scmax.out");
    int *best, *a, max, sol = 0, *poz, p, n, i, j;
    cin >> n;
    best = new int[n + 1];
    a = new int[n + 1];
    poz = new int[n + 1];

    for (i = 1; i <= n; i++){
        cin >> a[i];
    }


    best[n] = 1;
    poz[n] = -1;
    max = 1;
    p = n;

    for(i = n - 1; i >= 1; i--){
        best[i] = 1;
        poz[i] = -1;

        for(j = i + 1; j <= n; j++){

            if(a[i] < a[j] && best[i] < best[j] + 1){
                best[i] = best[j] + 1;
                poz[i] = j;

                if(best[i] > max){
                    max = best[i];
                    p=i;
                }

            }

        }

    }

    cout << max << "\n";
    i=p;

    while(i != -1){
        cout << a[i] << " ";
        i = poz[i];
    }

    return 0;
}