Cod sursa(job #1212619)

Utilizator meriniucrMeriniuc Razvan- Dumitru meriniucr Data 25 iulie 2014 13:22:03
Problema Subsir crescator maximal Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 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';
    maxim--;
    j=-1;
    for(int i=n-1; i>=0; i--){
        if(r[0][i] != maxim) continue;
        while(r[1][i] > -1){
            sir[++j]=a[i];
            i=r[1][i];
        }
        sir[++j]=a[i];
    }

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