# C++ - Longest Common Subsequence

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)

• edit your question and add a link to the programming challenge
– user228914
Dec 6 '20 at 6:08
• 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) Dec 6 '20 at 8:46
• @Damien I edited the code, but the program still exceeds 1000ms. Dec 6 '20 at 9:38
• @WhiteTiger Please don't make changes to your code after you get a suggestion. It isn't allowed.
– user228914
Dec 6 '20 at 9:40