Anonymous

//Longest ascending subsequence

#include <
fstream>
#include <
iostream>
#include <
vector>
using namespace std;
vector<
int>
vPred;
vector<
int>
a,v;
int imax;
void readData(ifstream& in)
{
int aux;
int i=1;
while(!in.eof())
{
in >
>
aux;
a.push_back(aux);
//Az a vektorba lessz az eredeti sorozat

}
}
void process()
{
int j,i,n;
v.push_back(1);
//A legelso elemnel 1 a hossza a sorozatnak

vPred.push_back(-1);
//A legelso elem elott nincs semmi

imax=0;
n=(int) a.size();
for(i=1;i<n;i++) 
{
v.push_back(1);
//az illeto elemet 1 re inicializaljuk

vPred.push_back(-1);
// az illeto elemnel -1 re inicializalunk majd ugyis atirjuk ha kell

for(j=0;j<i;j++)
{
if(a[j]<a[i] && v[j]+1>v[i]) // novekvo legyen es nagyobb mint az eddigi maximalis

{
v[i]=v[j]+1;
//noveljuk

vPred[i]=j;
//megjegyezuk a helyet hogy majd visszakereshessuk

}
}
if(v[i]>v[imax]) imax=i;
//uj maximalis ertekunk van, megjegyezzuk

}
}
void recoverSubstring(int i, ofstream &out)
{
//out << "Recovering substring..."<<endl;

if(vPred[i]+1!=0)
{ 
//out << "vPred["<<i<<"]+1!=0->"<<vPred[i]<<endl;

recoverSubstring(vPred[i],out);
}
//else out << "vPred["<<i<<"]+1=0->"<<vPred[i]<<endl;

out <
<
a[i] <
<
"
"
;
}
void writeData(ofstream &out)
{
out <
<
"
v:"
;
for(int i=0;i<(int)v.size()-1;i++) out <
<
v[i] <
<
"
"
;
out <
<
endl;
out <
<
"
vPred:"
;
for(int i=0;i<(int)vPred.size()-1;i++) out <
<
vPred[i] <
<
"
"
;
out <
<
endl;
out <
<
"
Hossza:"
;
out <
<
v[imax] <
<
endl;
out <
<
"
A sorozat: "
;
recoverSubstring(imax,out);
out <
<
endl<
<
"
Az eredeti:"
;
for(int i=0;i<(int)a.size()-1;i++) out <
<
a[i] <
<
"
"
;
}
int main()
{
ifstream in("ascending.in");
ofstream out("ascending.out");
readData(in);
process();
writeData(out);
return 0;
}