Cod sursa(job #817164)

Utilizator YoYoxxIftimesei Ioan YoYoxx Data 17 noiembrie 2012 13:35:28
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
using namespace std;
ifstream in("scmax.in");
ofstream out ("scmax.out");

int x[100001];
int mat[3][100001];
int ma=0,n;


void verificare(int w)
{
    int i,j;
        if(mat[1][n]>ma)
        {

            ma=mat[1][n];
            mat[2][0]=w;
            for (i=1;i<=n;i++)
                {
                    mat[2][i]=mat[1][i];

                }



        }




}

void rezolvare()
{
    int i,j,k;
    int a;
    for (i=1;i<=n;i++)
    {
        a=x[i];
        for(j=1;j<=n;j++)
        {
           // out<<a<<" "<<x[j]<<"\n";
           if (x[j]<a)
            {
               mat[1][j]=mat[1][j-1];
            }
                if (x[j]==a)
                {
                    mat[1][j]=mat[1][j-1];
                }
                    if (x[j]>a&&j>=i)
                    {
                        mat[1][j]=mat[1][j-1]+1;
                        a=x[j];
                    }


         verificare(x[i]);
        }
     /*  for (k=1;k<=n;k++)
       {
           out<<mat[1][k]<<" ";
       }
       out<<"\n";
       */

    }
}






int main()
{
    int i,j,a,b,k;
    in>>n;

    for (i=1;i<=n;i++)
    {
        in>>x[i];
    }
    rezolvare();


   out<<ma+1<<"\n";

  /* for (i=1;i<=n;i++)
   {
       out<<mat[2][i]<<" ";

   }*/
   out<<mat[2][0]<<" ";
   k=1;
   for (i=1;i<=n;i++)
   {
        if(mat[2][i]==k)
        {
            k++;
            out<<x[i]<<" ";
        }

   }


    return 0;
}