3
\$\begingroup\$

Link to the Problem

Here is my code to compute the length of the longest common subsequence of two integer arrays arr[] and brr[]:

#include <bits/stdc++.h>
using namespace std;
//Dynamic programm solution
int mem[10004][10004];//mem[i][j] stores length of the longest common subsequence, up to index i of arr and index j of brr 
vector<int> arr,brr;
int lcs(int i,int j){
    if (i<0||j<0) return 0;
    if (mem[i][j]!=-1) return mem[i][j];// if already computed, return mem[i][j]
    else {
        int tmp = 0;
        tmp = max(lcs(i-1,j),lcs(i,j-1));
        if (arr[i]==brr[j]) tmp = max(tmp,lcs(i-1,j-1)+1);
        mem[i][j] = tmp;
    }
    return mem[i][j];
}
main(){
    int n,m;// n,m are the length of the first and second array
    memset(mem,-1,sizeof(mem));
    cin >> n >> m;
    arr.resize(n+1);brr.resize(m+1);
    for (int i = 0;i<n;++i){
        cin >> arr[i];
    }
    for (int i = 0;i<m;++i){
        cin >> brr[i];
    }
    //calculate length of longest common subsequence of two array arr and brr
    cout << lcs(n-1,m-1);
}

The time complexity of the above approach is O(m*n). The running time of the program exceeds 1000ms when m and n are both as large as 10000. How can I improve the above program's speed to solve this problem in the case m = n = 10000 under 1000ms ? (I was trying to solve this problem in Codeforces, and there's a test case where m = n = 10000 and my program failed to solve it under 1000ms)

\$\endgroup\$
4
  • 3
    \$\begingroup\$ edit your question and add a link to the programming challenge \$\endgroup\$
    – user228914
    Dec 6 '20 at 6:08
  • 1
    \$\begingroup\$ A naive comment maybe: if ((arr[i]==brr[j]), then is not the solution always tmp = max(tmp,lcs(i-1,j-1)+1); ? If it is true, then we can avoid calculating lcs(i-1,j),lcs(i,j-1) \$\endgroup\$
    – Damien
    Dec 6 '20 at 8:46
  • \$\begingroup\$ @Damien I edited the code, but the program still exceeds 1000ms. \$\endgroup\$ Dec 6 '20 at 9:38
  • 2
    \$\begingroup\$ @WhiteTiger Please don't make changes to your code after you get a suggestion. It isn't allowed. \$\endgroup\$
    – user228914
    Dec 6 '20 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.