Pagini recente » Cod sursa (job #3194046) | Cod sursa (job #2425159) | Cod sursa (job #1380860) | Cod sursa (job #1351433) | Cod sursa (job #287009)
Cod sursa(job #287009)
#include<fstream>
using namespace std;
int n, t , a[5001], sis[5001], next[5001];
int minim, maxim , poz;
void Citire()
{
int i;
ifstream fin ("sis.in");
fin>>n;
for (i=1;i<=n;i++)
fin>>a[i];
fin.close();
}
void Sis()
{
int i,j,p;
sis[n]=1;next[n]=n+1;
for (i=n-1;i>=1;i--)
{
t=a[i];
minim=1000001;
p=n+1;
maxim=1000001;
for (j=i+1;j<=n;j++)
if ((t<=a[j])&&(a[j]<=minim)&&(maxim>sis[j]))
{
minim=a[j];
maxim=sis[j];
p=j;
}
if (p<=n)
{
sis[i]=1+maxim;
next[i]=p;
}
else
{
next[i]=n+1;
sis[i]=1;
}
}
minim=a[1]; poz = 1 ;
maxim=sis[1];
for (i=2;i<=n;i++)
if (minim>a[i])
{
minim=a[i];
if (maxim<=sis[i]) { maxim=sis[i]; poz = i ; }
}
}
void PrintSol()
{
//int i;
ofstream fout("sis.out");
fout<<maxim<<"\n";
while (poz<=n)
{
fout<<poz<<" " ;
poz = next[poz] ;
}
fout.close();
}
int main ()
{
Citire();
Sis();
PrintSol();
return 0;
}