Cod sursa(job #2299790)

Utilizator andaraluca2001Anda Epure andaraluca2001 Data 10 decembrie 2018 09:16:57
Problema Subsir crescator maximal Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
using namespace std;
int n, v[100001],best[100001],retine[100001];

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

int main()
{
    in>>n;

    for(int i=1;i<=n;i++) in>>v[i];

int vmax=0,indmax;
    for(int i=1;i<=n;i++)
    {
        int max=0;
        for(int j=1;j<i;j++) if(best[j]>max && v[j]<v[i]) max=best[j];
        best[i]=1+max;
        if(best[i]>vmax)
        {
            vmax=best[i];
            indmax=i;
        }
    }

    int cmax=vmax;
   out<<vmax<<'\n';
   retine[vmax]=indmax;
   for(int i=indmax-1;i>=1;i--)
   {
       if(best[i]==vmax-1 && v[i]<v[indmax])
       {

           vmax--;
           indmax=i;
           retine[vmax]=i;
       }

       if(vmax==0) break;

   }
    for(int i=1;i<=cmax;i++) out<<retine[i]<<" ";

    return 0;
}