Pagini recente » Cod sursa (job #2397343) | Cod sursa (job #894434) | Cod sursa (job #29081) | Cod sursa (job #2939409) | Cod sursa (job #360354)
Cod sursa(job #360354)
#include<fstream>
using namespace std;
int n, a[5001], sis[5001], next[5001];
int minim, poz;
void Citire()
{
int i;
ifstream fin ("subsir2.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--)
{
min=1000001;
p=n+1;
val=1000001;
for (j=i+1;j<=n;j++)
if ((min<sis[j])&&(a[i]<=a[j])&&(a[j]<val))
{
min=sis[j];
val=a[j];
p=j;
}
if (p<=n)
{
sis[i]=1+min;
next[i]=p;
}
else
{
next[i]=n+1;
sis[i]=1;
}
}
min=sis[1]; poz = 1 ;
for (i=2;i<=n;i++)
if (min>sis[i])
{
min=sis[i];
if (min<=sis[i]) { min=sis[i]; poz = i ; }
}
}
void PrintSol()
{
ofstream fout("subsir2.out");
fout<<maxim<<"\n";
while (poz<=n)
{
fout<<poz<<" " ;
poz = next[poz] ;
}
fout.close();
}
int main ()
{
Citire();
Sis();
PrintSol();
return 0;
}