Cod sursa(job #1098821)

Utilizator NacuCristianCristian Nacu NacuCristian Data 5 februarie 2014 11:33:50
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <stdio.h>

using namespace std;

int a[100001],n,rez[100001];



void citire()
{
    FILE *f1 =fopen("scmax.in","r");
    fscanf(f1,"%d",&n);
    for(int i=0;i<n;i++)
    {
        fscanf(f1,"%d",&a[i]);
    }
}

int pozma=0;
int maxim=0;
void dinamica()
{

    rez[n-1]=1;
    for(int i=n-2;i>=0;i--)
    {
        int ma=0;
        for(int j=n-1;j>i;j--)
        {
            if(a[i]<a[j] && rez[j]>ma)
            {
                ma=rez[j];

            }
        }
        if(ma+1>maxim)
        {
            maxim=ma+1;
            pozma=i;
        }
        rez[i]=ma+1;


    }
}

FILE *f2 = fopen("scmax.out","w");

void drum()
{
    fprintf(f2,"%d\n",maxim);
    int k=maxim;
    for(int i=pozma;i<n;i++)
        if(rez[i]==k)
        {
        fprintf(f2,"%d ",a[i]);
        k--;
        }




}


int main()
{
    citire();
    dinamica();
    drum();


    return 0;
}