Cod sursa(job #858680)

Utilizator rares123Zamfiriu Rares rares123 Data 19 ianuarie 2013 10:28:46
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
using namespace std;
int a[1000000],lg[1000000];
int main()
{
    int n;
    ifstream fin("scmax.in");
    ofstream fout("scmax.out");
    fin>>n;
    int max;
    for(int i=0;i<n;i++)
        fin>>a[i];
    lg[n-1]=1;
    for(int i=n-2;i>=0;i--)
        {
           max=0;
            for(int j=i+1;j<n;j++)
                if(lg[j]>max && a[j]>a[i])
                    max=lg[j];
            lg[i]=max+1;


        }
        max=0;
        int x;
        for(int i=0;i<n;i++)
          if(lg[i]>max)
          {
            max=lg[i];
            x=i;
          }
          cout<<lg[x]<<endl;
          cout<<a[x]<<" ";
     while(max)
     {
         for(int j=x+1;j<n;j++)
            if(lg[j]==max-1 && a[j]>a[x])
                {
                    cout<<a[j]<<" ";
                    x=j;
                }
            max--;
     }

    return 0;
}