Pagini recente » Cod sursa (job #1894379) | Cod sursa (job #825174) | Cod sursa (job #2862998) | Cod sursa (job #1910337) | Cod sursa (job #944127)
Cod sursa(job #944127)
#include <fstream>
#define In "subsir2.in"
#define Out "subsir2.out"
#define Nmax 5002
using namespace std;
int Lis[Nmax+2],prev[Nmax+2],a[Nmax+2],n,start,L;
bool viz[Nmax+2];
ofstream g(Out);
inline void Citire()
{
ifstream f(In);
f>>n;
for(int i=1;i<=n;i++)
f>>a[i];
f.close();
}
inline void Afisare(int x)
{
if(x!=Nmax)
{
Afisare(prev[x]);
g<<x<<" ";
}
}
inline void Dinamic()
{
int i,j,maxx,poz;
for(i=1;i<=n;i++)
{
maxx = 0;
poz = Nmax;
for(j=1;j<i;j++)
if(a[j]<=a[i])
{
if(Lis[j]>maxx)
{
maxx = Lis[j];
poz = j;
}
else
if(Lis[j]==maxx)
if(a[j]<a[poz])
poz = j;
}
Lis[i] = maxx+1;
prev[i] = poz;
viz[poz] = true;
}
L = Nmax;
for(i=1;i<=n;i++)
if(viz[i]==false)
{
if(Lis[i]<L)
{
L = Lis[i];
start = i;
}
else
if(Lis[i]==L && a[i]<a[start])
start = i;
}
g<<L<<"\n";
Afisare(start);
g<<"\n";
g.close();
}
int main()
{
Citire();
Dinamic();
return 0;
}