Cod sursa(job #2321758)

Utilizator rangrazvanRang Razvan Victor rangrazvan Data 16 ianuarie 2019 16:40:00
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    ifstream fin("scmax.in");
    ofstream fout("scmax.out");
    int n,*v,*d,*tata;
    fin>>n;
    v = new int[n];
    d = new int[n];
    tata = new int[n];
    for(int i=0;i<n;i++) {
        fin>>v[i];
        tata[i] = -1;
        d[i] = 1;
    }
    d[0] = 1;
    for(int i=1;i<n;i++){
        int maxi = 0,ind = -1;
        for(int j=i-1;j>=0;j--){
            if(v[j]<v[i] && d[j]>maxi){
                maxi = d[j];
                ind = j;
            }
        }
        if(ind!=-1){
            d[i] = maxi + 1;
            tata[i] = ind;
        }
    }
    int maxi = 0,ind;
    for(int i=0;i<n;i++){
        if(d[i]>maxi){
            maxi = d[i];
            ind = i;
        }
    }
    fout<<maxi<<endl;
    int *rez,nr=0;
    rez = new int[n];
    while(tata[ind]!=-1){
        rez[nr] = v[ind];
        nr++;
        ind = tata[ind];
    }
    rez[nr] = v[ind];
    nr++;
    for(int i=nr-1;i>=0;i--){
        fout<<rez[i]<<" ";
    }
    return 0;
}