Cod sursa(job #1212623)

Utilizator meriniucrMeriniuc Razvan- Dumitru meriniucr Data 25 iulie 2014 13:28:55
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>

using namespace std;

ifstream mama("scmax.in");
ofstream tata("scmax.out");

int a[100001], minim[2][100001], r[2][100001],n, sir[100001];

int main()
{
    mama>>n;
    for(int i=0; i<n; i++)
        mama>>a[i];

    int j=0, maxim=1;
    minim[0][0]=a[0];
    r[1][0]=-1;

    for(int k, i=1; i<n; i++){
        k=j;
        if(a[i]>minim[0][j]) { r[0][i]=j+1; r[1][i]=minim[1][j]; minim[0][j+1]=a[i]; minim[1][j+1]=i; j++; maxim=j+1;}
            else
            {
                while(a[i] <= minim[0][j] and j > -1)
                    j--;
                r[0][i]=j+1;  minim[0][j+1]=a[i]; minim[1][j+1]=i;
                if(j == -1) r[1][i]=-1;
                    else r[1][i]=minim[1][j];
                j=k;
            }
    }
    tata<<maxim<<'\n';
    if(maxim > 1){
        maxim--;
        j=-1;
        bool ok=true;
        for(int i=n-1; i>=0 and ok; i--){
            if(r[0][i] != maxim) continue;
            while(r[1][i] > -1){
                sir[++j]=a[i];
                i=r[1][i];
                ok=false;
            }
            sir[++j]=a[i];
        }

        for(int i=j; i>=0; i--)
            tata<<sir[i]<<" ";
    }

        else tata<<a[0];
    return 0;
}