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];
    int n,m;// n,m are the length of the first and second array
    cin >> n >> m;
    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)

  • 3
    \$\begingroup\$ edit your question and add a link to the programming challenge \$\endgroup\$
    – user228914
    Commented Dec 6, 2020 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
    Commented Dec 6, 2020 at 8:46
  • \$\begingroup\$ @Damien I edited the code, but the program still exceeds 1000ms. \$\endgroup\$ Commented Dec 6, 2020 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
    Commented Dec 6, 2020 at 9:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.