Subsir comun de valoare maxima

[•Mitza444]

Salut! Am doua siruri cu cifre X,Y de lungime n respectiv m si vreau sa aflu cel mai lung subsir comun de valoare maxima.Am facut cel mai lung subsir comun cu algoritmul clasic ,dar nu stiu cum pot reconstitui cel mai lung subsir cu valoare maxima. .Am incercat urmatoarea varianta dar nu merge in toate cazurile.Cum as putea face sa mearga ??

Cod:

    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++)
            if(X[i]==Y[j])
                SC[i][j]=1+SC[i-1][j-1];//cel mai lung
            else
                SC[i][j]=max(SC[i][j-1],SC[i-1][j]);//subsir comun
    }
pmx=n;pmy=m;
    for(k=SC[n][m];k>=1;k--){//caut pozitia de lungime k cu cea mai mare cifra
        mx=-1;
        for(i=pmx;i>=1;i--)
            for(j=pmy;j>=1;j--)
                if(SC[i][j]==k && X[i]==Y[j] && X[i]>mx){
                    mx=X[i];pmx2=i;pmy2=j;
                }
       sol[++sol[0]]=mx;//retin maximul
       pmx=pmx2;pmy=pmy2;
    }
    for(i=sol[0];i>=1;i--)
        printf("%d",sol[i]);
    printf("\n");

[•freak93]

In general e mai bine sa explici cum faci. Astfel pentru oricine ar fi mai usor sa se gandeasca la ideea ta decat sa se uite prin sursa ta.

[•Mitza444]

Ok,scuze.Pai algoritmul de cel mai lung subsir e cel clasic.La reconstituire eu pornesc de la lungimea maxima k pana la 1 si caut poz i,j pe care X[ i ] ==Y [ j ] si SC[ i] [ j ] == k si daca X[ i ] e mai mare decat max-ul gasit pana atunci inlocuiesc maximul si retin pozitiile i,j in pmx2 respectiv pmy2.Cand caut un alt element maxim incep de la pozitia maxima gasita anterior pmx,pmy pt. a nu lua o valore maxima din alt subsir in cel curent. Aici e problema ca imi pune pune alte valori maxime din alte subsiruri cu conditia curenta, si nu-mi dau seama unde gresesc si cum as putea pune conditia astfel incat sa le ia corect.

Apropo problema e aceasta : http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=948
Multumesc.

[•SpiderMan]

Uite aici explica algoritmul, ai teste si surse oficiale si poti sa-ti testezi sursa, singura diferenta aici este ca citesti numerele despartite printr-un "spatiu", si sunt numere nu doar cifre (din cate vad eu). Spor la treaba.

[•visanr]

Nu e acelasi lucru, in arhiva educationala iti cere un subsir comun maximal oarecare, iar la problema de pe campion iti cere un subsir comun maximal care ti-ar da valoarea maxima.