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;
}