Cod sursa(job #2387496)

Utilizator bluestorm57Vasile T bluestorm57 Data 24 martie 2019 19:32:03
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int n;
int v[100005],best[100005],poz[100005],cmax,pozmax;
char s[500000001];

void see(int x){
    g<<v[x]<<" ";
    if(poz[x]!=-1 && poz[x]<=n)
        see(poz[x]);
}

void made(){
    int j=1,i;
    int n=strlen(s);
    for(i=0; i<n; i++)
        if(s[i]>='0' && s[i]<='9'){
            v[j]=v[j]*10+s[i]-'0';
            i++;


            while(s[i]>='0' && s[i]<='9'){
               v[j]=v[j]*10+s[i]-'0';
               i++;
            }

            j++;
        }
}

int main(){
    int i,j;
    f>>n;
    f.get();

    f.getline(s,5000001);
    made();
   // for(i=1; i<=n; i++)
     // g<<v[i]<<" ";

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

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

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

                if(cmax<best[i]){
                    cmax=best[i];
                    pozmax=i;
                }
            }
    }
    g<<cmax<<"\n";
    see(pozmax);


    return 0;
}