Pagini recente » Cod sursa (job #2894585) | Cod sursa (job #143976) | Cod sursa (job #1638744) | Cod sursa (job #2884464) | Cod sursa (job #944077)
Cod sursa(job #944077)
#include <fstream>
#define In "subsir2.in"
#define Out "subsir2.out"
#define Nmax 5002
using namespace std;
int Lis[Nmax],prev[Nmax],a[Nmax],n,start,L;
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;
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;
}