Cod sursa(job #1821301)

Utilizator savigunFeleaga Dragos-George savigun Data 2 decembrie 2016 21:27:41
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    ifstream cin("scmax.in");
    ofstream cout("scmax.out");
    int n, i, j, *v, *best, *pos, lmax = 0, posmax;

    cin>>n;
    v = new int[n+1];
    best = new int[n+1];
    pos = new int[n+1]();

    for(i = 1; i <= n; ++i)
        cin>>v[i];

    best[1] = 1;

    for(i = 2; i <= n; ++i){
        int cmax = 0;
        best[i] = 1;
        for(j = 1; j < i; ++j){
            if(v[j] < v[i]){
                if(best[j] > cmax){
                    cmax = best[j];
                    best[i] = 1 + best[j];
                    pos[i] = j;

                    if(best[i] > lmax){
                        lmax = best[i];
                        posmax = i;
                    }

                }
            }
        }
    }

    cout<<lmax<<"\n";

    int *s, f = 0;
    s = new int[n+1];
    while(posmax > 0){
        s[++f] = v[posmax];
        posmax = pos[posmax];
    }

    for(i = f; f >= 1; --f)
        cout<<s[f]<<" ";

    return 0;
}