# LCS

longest common subsequence

dp的精神:從後往前考慮，每次考慮最後一個的情況

## 想法
Consider two sequence a and b
> If a[i]==b[j], it is better to choose, so dp[i][j]=dp[i-1][j-1]+1
> If a[i]! =b[j], can't choose any for lcs, drop a[i] or b[j], so dp[i][j]=max(dp[i-1][j],dp[i][j-1])

int lcs(int i=n,int j=m){
    if(i<0 || j<0) return 0; //out of range
    int chose=0,not_chose=0;
    if(a[i]==b[j]) chose=lcs(i-1,j-1)+1; //選擇當lcs
    not_chose=max(lcs(i-1,j),lcs(i,j-1)); //選擇丟哪個元素會對答案比較有幫助
    return max(chose,not_chose);  //選擇最佳解
}              

**Top-down**
但由於這樣做太慢了所以我們可以記錄算過的答案，下次遇到就直接回傳算完的答案，也就是標準的dp的top-down做法
> 如果之前有算過就直接回傳之前的答案
> 如果沒有計算過則往下計算,並把答案存起來,再回傳

int lcs(int i=n,int j=m){
    if(i<0 || j<0) return 0;
    if(ans[i][j]!=-1) return ans[i][j];  //如果之前有算過答案就直接回傳
    int chose=0,not_chose=0;
    if(a[i]==b[j]) chose=lcs(i-1,j-1)+1; 
    not_chose=max(lcs(i-1,j),lcs(i,j-1)); 
    ans[i][j]=max(chose,not_chose); //先把答案存起來給之後查詢
    return ans[i][j];
}

**Botton-up**
DP的另一種寫法:bottom-up，直接改用迴圈，可省去遞迴呼叫的時間
> 由於每次都會往前面(i-1 or j-1)遞迴，所以迴圈寫法就是先把前面的算好，從下往上計算，故稱bottom-up

注意:不能用0-based，因為ans在一開始跑時(i-1 or j-1)會出界

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        int chose=0,not_chose=0;
        if(a[i]==b[j]) chose=ans[i-1][j-1]+1; 
        not_chose=max(ans[i-1][j],ans[i][j-1]);
        ans[i][j]=max(chose,not_chose);
    }
}

最後答案就是放在ans[n][m]這格

## 加速(NlogN)

使用技巧：lcs轉lis

Step1. 紀錄b陣列中元素值為x的所有index
Step2. 依照a陣列中的順序，依序把該元素在b中的index反向(大到小)加到c陣列裡
Step3. 求c的lis，及a跟b的lcs

int n,m;
while(cin >> n >> m && n && m){
    vector<int> a(n),b(m);
    for(auto &i:a) cin >> i;
    for(auto &i:b) cin >> i;

    //Step 1
    vector<vector<int>> idx(MAXN);
    for(int i=0;i<m;i++){
        idx[b[i]].push_back(i);
    }
    
    //Step 2
    vector<int> c;
    for(int i=0;i<n;i++){
        for(auto it=idx[a[i]].rbegin();it!=idx[a[i]].rend();it++){
            c.push_back(*it);
        }
    }
    
    //Step 3
    vector<int> lis;
    for(auto i:c){
        if(lis.empty() || lis.back()<i) lis.push_back(i);
        else *lower_bound(all(lis),i)=i;
    }
    cout << lis.size() << '\n';  //lis=lcs
}