Problema programare dinamica

[•fulgerulnegru]

Am o mica problema de a optimiza codul ca sa imi dea raspunsul corect:

Sa se gaseasca secventa de lungime maxima care este lexicografic cel mai mare

Exemplu
IN.in

7145
847835
out.out
7 5

in2.in

4175
874835

out2.out
7 5

Eu am facut codul pentru partea de programare dinamic dar nu stiu cum sa fac si partea de lexicografie

Cod:

#include<iostream>
#include<vector>
#include<string>
#include<fstream>
using namespace std;
ifstream in("in.in");
vector<vector<int> >v;
string s1,s2;
//calculeaza cel mai lung subsir comun
//dar  nu si cel mai mare valoare care o cere in problema
void dinamic(){
    int i,j;
    //construirea matricei pe baza recurente programari dinamice
    for(i=1;i<s1.size()+1;i++)
        for(j=1;j<s2.size()+1;j++){
            if(s1[i-1]==s2[j-1])
                v[i][j]=1+v[i-1][j-1];
            else
                v[i][j]=max(v[i-1][j],v[i][j-1]);
        }
    i--;j--;
    //gasirea subsirului de lungime maxima
    while(i>0||j>0){
        if(i>0&&j>0&&s1[i-1]==s2[j-1]){
            cout<<s1[i-1]<<" ";
            i--;j--;
            continue;
        }
        if(i&&v[i][j]==v[i-1][j]){
            i--;
            continue;
        }
        if(j&&v[i][j]==v[i][j-1])
            j--;
    }
    cout<<"\n";
    for(i=1;i<s1.size()+1;i++){
        for(j=1;j<s1.size()+1;j++)
            cout<<v[i][j]<<" ";
        cout<<"\n";
    }
}
int main (){
    in>>s1>>s2;
    v.resize(s1.size()+1);
    int i;
    for(i=0;i<s1.size()+1;i++){
        v[i].resize(s2.size()+1);
    }
    dinamic();
    return 0;
}

[•nparfene2004]

Banuiesc din ce ai scris ca te intereseaza subsirul comun de lungime maxima cel mai mare lexicografic.
Ei bine, ca sa rezolvi corect trebuie sa construiesti matricea bottom-up, adica il calculezi pe a(i,j) in functie de a[i+1,j] si a[i,j+1]. Pentru constituirea solutiei maxime lexicografic pornesti acum top-down, adica de la pozitia (1,1) la (m,n)

[•fulgerulnegru]

dar nu se intampla aceasi problema si dac plec din 1,1 sau din n,m
Ca vei acea la stanga o valoare si la dreapta tot la valorea si atunci trebuie sa alegi elemntul cu valoare mai mare

[•nparfene2004]

Nu se intampla la fel. Daca vreau minim sau maxim lexicografic, plec de la stanga la dreapta cu comparatiile si in niciun caz invers. Gandeste-te ca asa e si cu 2 siruri. Cand le compari lexicografic pleci de la stanga la dreapta

[•fulgerulnegru]

Sa zicem ca asa e corect din punctul de vedere, dar eu construiesc o matrice care in directia stanga imi da o  valoare si in directia jos imi da aceasi valoare acum in ce sens merg

[•tsuby]

A gasit cineva o solutie si sa o poata explica? Am incercat cum a spus Narcis, insa nu am reusit sa o fac sa mearga.