Cod sursa(job #912486)

Utilizator VladMSBonta vlad valentin VladMS Data 12 martie 2013 14:27:11
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int i,j,n,v[5001],l[5001],t[5001],poz,minn,maxx,pozmax;
int main()
{
    fin>>n;
    for(i=1;i<=n;++i)
        fin>>v[i];
    for(i=n;i>=1;--i)
    {
        poz=0;
        minn=0;
        for(j=i+1;j<=n;++j)
            if(v[i]<=v[j])
            {
                if(l[j]>minn||poz==0)
                        {
                            minn=l[j];
                            poz=j;
                        }
                    else
                    if(l[j]==minn&&v[j]<v[poz])
                        {
                            poz=j;
                        }
            }
        if(poz!=0)
        {
            if(l[poz]==0)
                l[i]=minn+2;
            else
                l[i]=minn+1;
            t[i]=poz;
            if(l[i]>maxx)
                {maxx=l[i];
                 pozmax=i;
                }
        }
        else
        {
            l[i]=1;
            t[i]=i;
        }
    }
    fout<<maxx<<'\n';
    while(t[pozmax]!=pozmax)
        {
            fout<<pozmax<<" ";
            pozmax=t[pozmax];
        }
    fout<<t[pozmax]<<" ";
    return 0;
}