最大子序列

最大子序列是要找出由數(shù)組成的一維數(shù)組中和最大的連續(xù)子序列。比如{5,-3,4,2}的最大子序列就是 {5,-3,4,2}，它的和是8,達(dá)到最大；而 {5,-6,4,2}的最大子序列是{4,2}，它的和是6。你已經(jīng)看出來了，找最大子序列的方法很簡單，只要前i項的和還沒有小于0那么子序列就一直向后擴展，否則丟棄之前的子序列開始新的子序列，同時我們要記下各個子序列的和，最后找到和最大的子序列。

代碼如下：

?

#include<iostream> #include<vector> using namespace std; int maxSubSum(const vector<int> & arr,int &begin,int &end){int maxSum=0;int currSum=0;int newbegin=0;for(int i=0;i<arr.size();++i){currSum+=arr[i];if(currSum>maxSum){maxSum=currSum;begin=newbegin;end=i;}if(currSum<0){currSum=0;newbegin=i+1;}}return maxSum; }int main(){int len;cout<<"Input array length"<<endl;cin>>len;cout<<"Input an integer vector"<<endl;vector<int> arr;int a;for(int i=0;i<len;++i){cin>>a;arr.push_back(a);}int begin,end;cout<<maxSubSum(arr,begin,end)<<endl;for(int i=begin;i<=end;++i)cout<<arr[i]<<" ";cout<<endl;return 0; }

最長遞增子序列

?比如arr={1,5,8,2,3,4}的最長遞增子序列是1,2,3,4

動態(tài)規(guī)劃的思想，考慮{arr[0],...,arr[i]}的最長遞增子序列時需要找到所有比arr[i]小的arr[j]，且j<i，結(jié)果應(yīng)該是所有{arr[0],...,arr[j]}的最長遞增子序列中最長的那一個再加1。即我們需要一個輔助的數(shù)組aid_arr，aid_arr[i]的值是{arr[0],...,arr[i]}的最長遞增子序列的長度，aid_arr[0]=1。

?

#include<iostream> #include<stack> #include<vector> using?namespace?std; int?main(){ ????const?int?len=14; ????int?arr[len]={1,9,3,8,11,4,5,6,4,1,9,7,1,7}; ????vector<int> vec(&arr[0],&arr[len]); ????vector<int> monoseqlen(len,1); ????vector<int> preindex(len,-1); ????int?maxmonoseqlen=-1; ????int?maxmonoindex=-1; ????for(int?i=1;i<len;++i){ ????????int?curr=vec[i]; ????????for(int?j=0;j<i;++j){ ????????????if(vec[j]<vec[i]){ ????????????????int?msl=monoseqlen[j]+1; ????????????????if(msl>monoseqlen[i]){ ????????????????????monoseqlen[i]=msl; ????????????????????preindex[i]=j; ????????????????} ????????????} ????????} ????} ????for(int?i=0;i<len;++i){ ????????if(monoseqlen[i]>maxmonoseqlen){ ????????????maxmonoseqlen=monoseqlen[i]; ????????????maxmonoindex=i; ????????} ????} ????stack<int> st; ????while(maxmonoindex>=0){ ????????st.push(vec[maxmonoindex]); ????????maxmonoindex=preindex[maxmonoindex]; ????} ????vector<int> rect; ????while(!st.empty()){ ????????rect.push_back(st.top()); ????????st.pop(); ????}?? ????vector<int>::iterator itr=rect.begin(); ????while(itr!=rect.end()){ ????????cout<<*itr++<<"\t"; ????} ????cout<<endl; ????return?0; }

最長公共子串（LCS）

找兩個字符串的最長公共子串，這個子串要求在原字符串中是連續(xù)的。其實這又是一個序貫決策問題，可以用動態(tài)規(guī)劃來求解。我們采用一個二維矩陣來記錄中間的結(jié)果。這個二維矩陣怎么構(gòu)造呢？直接舉個例子吧："bab"和"caba"(當(dāng)然我們現(xiàn)在一眼就可以看出來最長公共子串是"ba"或"ab")

　　 b　　a　　b

c　　0　　0　　0

a　　0　　1　　0

b　　1　　0　　1

a　　0　　1　　0

我們看矩陣的斜對角線最長的那個就能找出最長公共子串。

不過在二維矩陣上找最長的由1組成的斜對角線也是件麻煩費時的事，下面改進(jìn)：當(dāng)要在矩陣是填1時讓它等于其左上角元素加1。

　　 b　　a　　b

c　　0　　0　　0

a　　0　　1　　0

b　　1　　0　　2

a　　0　　2　　0

這樣矩陣中的最大元素就是 最長公共子串的長度。

在構(gòu)造這個二維矩陣的過程中由于得出矩陣的某一行后其上一行就沒用了，所以實際上在程序中可以用一維數(shù)組來代替這個矩陣。

代碼如下：

?

#include<iostream> #include<cstring> #include<vector> using?namespace?std; //str1為橫向，str2這縱向 const?string LCS(const?string& str1,const?string& str2){ ????int?xlen=str1.size();?????? //橫向長度 ????vector<int> tmp(xlen);??????? //保存矩陣的上一行 ????vector<int> arr(tmp);???? //當(dāng)前行 ????int?ylen=str2.size();?????? //縱向長度 ????int?maxele=0;?????????????? //矩陣元素中的最大值 ????int?pos=0;????????????????? //矩陣元素最大值出現(xiàn)在第幾列 ????for(int?i=0;i<ylen;i++){ ????????string s=str2.substr(i,1); ????????arr.assign(xlen,0);???? //數(shù)組清0 ????????for(int?j=0;j<xlen;j++){ ????????????if(str1.compare(j,1,s)==0){ ????????????????if(j==0) ????????????????????arr[j]=1; ????????????????else ????????????????????arr[j]=tmp[j-1]+1; ????????????????if(arr[j]>maxele){ ????????????????????maxele=arr[j]; ????????????????????pos=j; ????????????????} ????????????}?????? ????????} //????? { //????????? vector<int>::iterator iter=arr.begin(); //????????? while(iter!=arr.end()) //????????????? cout<<*iter++; //????????? cout<<endl; //????? } ????????tmp.assign(arr.begin(),arr.end()); ????} ????string res=str1.substr(pos-maxele+1,maxele); ????return?res; } int?main(){ ????string str1("21232523311324"); ????string str2("312123223445"); ????string lcs=LCS(str1,str2); ????cout<<lcs<<endl; ????return?0; }

?

最長公共子序列

最長公共子序列與最長公共子串的區(qū)別在于最長公共子序列不要求在原字符串中是連續(xù)的，比如ADE和ABCDE的最長公共子序列是ADE。

我們用動態(tài)規(guī)劃的方法來思考這個問題如是求解。首先要找到狀態(tài)轉(zhuǎn)移方程：

符號約定，C1是S1的最右側(cè)字符，C2是S2的最右側(cè)字符，S1‘是從S1中去除C1的部分，S2'是從S2中去除C2的部分。

LCS(S1,S2)等于下列3項的最大者：

（1）LCS（S1，S2’）

（2）LCS（S1’，S2）

（3）LCS（S1’，S2’）--如果C1不等于C2； LCS（S1'，S2'）+C1--如果C1等于C2；

邊界終止條件：如果S1和S2都是空串，則結(jié)果也是空串。

下面我們同樣要構(gòu)建一個矩陣來存儲動態(tài)規(guī)劃過程中子問題的解。這個矩陣中的每個數(shù)字代表了該行和該列之前的LCS的長度。與上面剛剛分析出的狀態(tài)轉(zhuǎn)移議程相對應(yīng)，矩陣中每個格子里的數(shù)字應(yīng)該這么填，它等于以下3項的最大值：

（1）上面一個格子里的數(shù)字

（2）左邊一個格子里的數(shù)字

（3）左上角那個格子里的數(shù)字（如果 C1不等于C2）； 左上角那個格子里的數(shù)字+1（ 如果C1等于C2）

舉個例子：

?　　　　 ?G　　C　　T　　A

　　 0　　0　　0　　0　　0

G　 0　　1　　1　　1　　1

B　 0　　1　　1　　1　　1

T　 0　　1　　1　　2　　2

A ? ?0　　1　　1　　2　　3

填寫最后一個數(shù)字時，它應(yīng)該是下面三個的最大者：

（1）上邊的數(shù)字2

（2）左邊的數(shù)字2

（3）左上角的數(shù)字2+1=3,因為此時C1==C2

所以最終結(jié)果是3。

在填寫過程中我們還是記錄下當(dāng)前單元格的數(shù)字來自于哪個單元格，以方便最后我們回溯找出最長公共子串。有時候左上、左、上三者中有多個同時達(dá)到最大，那么任取其中之一，但是在整個過程中你必須遵循固定的優(yōu)先標(biāo)準(zhǔn)。在我的代碼中優(yōu)先級別是左上>左>上。

下圖給出了回溯法找出LCS的過程：

奉上代碼：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78

#include<iostream> #include<cstring> #include<stack> #include<utility> #define LEFTUP 0 #define LEFT 1 #define UP 2 using?namespace?std; int?Max(int?a,int?b,int?c,int?*max){????????????//找最大者時a的優(yōu)先級別最高，c的最低.最大值保存在*max中 ????int?res=0;??????????//res記錄來自于哪個單元格 ????*max=a; ????if(b>*max){ ????????*max=b; ????????res=1; ????} ????if(c>*max){ ????????*max=c; ????????res=2; ????} ????return?res; } //調(diào)用此函數(shù)時請注意把較長的字符串賦給str1,這主要是為了在回溯最長子序列時節(jié)省時間。如果沒有把較長的字符串賦給str1不影響程序的正確執(zhí)行。 string LCS(const?string &str1,const?string &str2){ ????int?xlen=str1.size();???????????????//橫向長度 ????int?ylen=str2.size();???????????????//縱向長度 ????if(xlen==0||ylen==0)????????????????//str1和str2中只要有一個為空，則返回空 ????????return?""; ????pair<int,int> arr[ylen+1][xlen+1];????//構(gòu)造pair二維數(shù)組，first記錄數(shù)據(jù)，second記錄來源 ????for(int?i=0;i<=xlen;i++)?????????//首行清0 ????????arr[0][i].first=0; ????for(int?j=0;j<=ylen;j++)?????????//首列清0 ????????arr[j][0].first=0; ????for(int?i=1;i<=ylen;i++){ ????????char?s=str2.at(i-1); ????????for(int?j=1;j<=xlen;j++){ ????????????int?leftup=arr[i-1][j-1].first; ????????????int?left=arr[i][j-1].first; ????????????int?up=arr[i-1][j].first; ????????????if(str1.at(j-1)==s)?????????//C1==C2 ????????????????leftup++; ????????????int?max; ????????????arr[i][j].second=Max(leftup,left,up,&arr[i][j].first); //????????? cout<<arr[i][j].first<<arr[i][j].second<<" "; ????????} //????? cout<<endl; ????}???????/*矩陣構(gòu)造完畢*/ ????//回溯找出最長公共子序列 ????stack<int> st; ????int?i=ylen,j=xlen; ????while(i>=0&&j>=0){ ????????if(arr[i][j].second==LEFTUP){ ????????????if(arr[i][j].first==arr[i-1][j-1].first+1) ????????????????st.push(i); ????????????--i; ????????????--j; ????????} ????????else?if(arr[i][j].second==LEFT){ ????????????--j; ????????} ????????else?if(arr[i][j].second==UP){ ????????????--i; ????????} ????} ????string res=""; ????while(!st.empty()){ ????????int?index=st.top()-1; ????????res.append(str2.substr(index,1)); ????????st.pop(); ????} ????return?res; } int?main(){ ????string str1="GCCCTAGCG"; ????string str2="GCGCAATG"; ????string lcs=LCS(str1,str2); ????cout<<lcs<<endl; ????return?0; }

下面給一個Java版本

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

public?static?<E> List<E> longestCommonSubsequence(E[] s1,E[] s2){ ????????int[][] num=new?int[s1.length+1][s2.length+1]; ????????for(int?i=1;i<s1.length+1;i++){ ????????????for(int?j=1;j<s2.length+1;j++){ ????????????????if(s1[i-1].equals(s2[j-1])){ ????????????????????num[i][j]=1+num[i-1][j-1]; ????????????????} ????????????????else{ ????????????????????num[i][j]=Math.max(num[i-1][j],num[i][j-1]); ????????????????} ????????????} ????????} ????????System.out.println("lenght of LCS= "+num[s1.length][s2.length]); ????????int?s1position=s1.length,s2position=s2.length; ????????List<E> result=new?LinkedList<E>(); ????????while(s1position>0?&& s2position>0){ ????????????if(s1[s1position-1].equals(s2[s2position-1])){ ????????????????result.add(s1[s1position-1]); ????????????????s1position--; ????????????????s2position--; ????????????} ????????????else?if(num[s1position][s2position-1]>=num[s1position-1][s2position]){ ????????????????s2position--; ????????????} ????????????else{ ????????????????s1position--; ????????????} ????????} ????????Collections.reverse(result); ????????return?result; ????}

std::endl是一個特殊值，稱為操縱符（manipulator），將它寫入輸出流時具有輸出換行的效果，并刷新與設(shè)備相關(guān)聯(lián)的緩沖區(qū)(buffer)。通過刷新緩沖區(qū)用戶可立即看到寫入到流中的輸出。

我在調(diào)試以上代碼時在45行（cout<<endl;）處設(shè)置斷點，結(jié)果發(fā)現(xiàn)“43行（cout<<arr[i][j].first<<arr[i][j].second<<" ";） 沒有執(zhí)行”，這就是因為43行末尾沒有加endl，所以用戶沒有立即看到輸出流中的數(shù)據(jù)。

字符串編輯距離

?要想把字符串S1變成S2，可以經(jīng)過若干次下列原子操作：

1.刪除一個字符

2.增加一個字符

3.更改一個字符

字符串S1和S2的編輯距離定義為從S1變成S2所需要原子操作的最少次數(shù)。

解法跟上面的最長公共子序列十分相似，都是動態(tài)規(guī)劃，把一個問題轉(zhuǎn)換為若干個規(guī)模更小的子問題，并且都借助于一個二維矩陣來實現(xiàn)計算。

約定：字符串S去掉最后一個字符T后為S'，T1和T2分別是S1和S2的最后一個字符。

則dist(S1,S2)是下列4個值的最小者：

1.dist(S1',S2')--當(dāng)T1==T2

2.1+dist(S1',S2)--當(dāng)T1!=T2，并且刪除S1的最后一個字符T1

3.1+dist(S1,S2')--當(dāng)T1!=T2，并且在S1后面增加一個字符T2

4.1+dist(S1',S2')--當(dāng)T1!=T2，并且把S1的最的一個字符T1改成T2

?

把問題轉(zhuǎn)換為二維矩陣：

arr[i][j]表示S1.sub(0,i)和S2.sub(0,j)的編輯距離，則

arr[i][j]=min{1+arr[i][j-1], 1+arr[i-1][j], 1+arr[i-1][j-1](當(dāng)S1[i]!=S2[j]), arr[i-1][j-1](當(dāng)S1[i]==S2[j])}

邊界情況：arr[0][j]=j, arr[i][0]=i

代碼就不寫了，跟最長公共子序列很相似。

?

計算兩個字條串的相似度除了Edit Distance，還有一種方法是計算Jaro Distance。具體怎么算讀者可以搜一下。

總結(jié)

以上是生活随笔為你收集整理的最大子序列、最长递增子序列、最长公共子串、最长公共子序列、字符串编辑距离的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。