Pagini recente » Cod sursa (job #3221075) | Cod sursa (job #645012) | Cod sursa (job #2516230) | Cod sursa (job #2160059) | Cod sursa (job #25903)
Cod sursa(job #25903)
#include<fstream.h>
int N, a[1000], sol[1000], ant[1000];
void citire ()
{
ifstream f("subsir.in");
f>>N;
for(int i=1;i<=N;i++)
f>>a[i];
f.close();
}
void dinamica ()
{
sol[1]=1;
ant[1]=-1;
for(int i=2;i<=N;i++)
{
int max=0,maxj;
for(int j=1;j<i;j++)
if (sol[j]>=max && a[j]<=a[i])
if (sol[j]==max && a[j]<=a[maxj])
{
max=sol[j];
maxj=j;
}
else
{
max=sol[j];
maxj=j;
}
if(max!=0)
{
sol[i]=max+1;
ant[i]=maxj;
}
else
{
sol[i]=1;
ant[i]=-1;
}
}
}
void afisare ()
{
ofstream g("subsir.out");
int max=0,x=1;
for (int i=1;i<=N;i++)
{
if(sol[i]>max)
{
max=sol[i];
x=i;
}
if (sol[i]==max && a[i]<a[x])
{
max=sol[i];
x=i;
}
}
int solutie[1000],y=0;
while (ant[x]!=-1)
{
y++;
solutie[y]=x;
x=ant[x];
}
y++;
solutie[y]=x;
g<<y<<'\n';
for(int k=y;k>=1;k--)
g<<solutie[k]<<' ';
g.close();
}
int main ()
{
citire();
dinamica();
afisare();
return 0;
}