原文链接:/s/blog_54f82cc0zi4b.html
最大子序列
最大子序列是要找出由数组成的一维数组中和最大的连续子序列。比如{5,-3,4,2}的最大子序列就是 {5,-3,4,2},它的和是8,达到最大;而 {5,-6,4,2}的最大子序列是{4,2},它的和是6。你已经看出来了,找最大子序列的方法很简单,只要前i项的和还没有小于0那么子序列就一直向后扩展,否则丢弃之前的子序列开始新的子序列,同时我们要记下各个子序列的和,最后找到和最大的子序列。
代码如下:
最长公共子串(LCS)
找 两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。其实这又是一个序贯决策问题,可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结 果。这个二维矩阵怎么构造呢?直接举个例子吧:"bab"和"caba"(当然我们现在一眼就可以看出来最长公共子串是"ba"或"ab")
bab
c000
a010
b101
a010
我们看矩阵的斜对角线最长的那个就能找出最长公共子串。
不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事,下面改进:当要在矩阵是填1时让它等于其左上角元素加1。
bab
c000
a010
b102
a020
这样矩阵中的最大元素就是 最长公共子串的长度。
在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了,所以实际上在程序中可以用一维数组来代替这个矩阵。
代码如下:
最长公共子序列
最长公共子序列与最长公共子串的区别在于最长公共子序列不要求在原字符串中是连续的,比如ADE和ABCDE的最长公共子序列是ADE。
我们用动态规划的方法来思考这个问题如是求解。首先要找到状态转移方程:
等号约定,C1是S1的最右侧字符,C2是S2的最右侧字符,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都是空串,则结果也是空串。
下面我们同样要构建一个矩阵来存储动态规划过程中子问题的解。这个矩阵中的每个数字代表了该行和该列之前的LCS的长度。与上面刚刚分析出的状态转移议程相对应,矩阵中每个格子里的数字应该这么填,它等于以下3项的最大值:
(1)上面一个格子里的数字
(2)左边一个格子里的数字
(3)左上角那个格子里的数字(如果 C1不等于C2); 左上角那个格子里的数字+1( 如果C1等于C2)
举个例子:
00000
G 01111
B 01111
T 01122
A
填写最后一个数字时,它应该是下面三个的最大者:
(1)上边的数字2
(2)左边的数字2
(3)左上角的数字2+1=3,因为此时C1==C2
所以最终结果是3。
在填写过程中我们还是记录下当前单元格的数字来自于哪个单元格,以方便最后我们回溯找出最长公共子串。有时候左上、左、上三者中有多个同时达到最大,那么任取其中之一,但是在整个过程中你必须遵循固定的优先标准。在我的代码中优先级别是左上>左>上。
奉上代码:
下面给一个Java版本
?
std::endl是一个特殊值,称为操纵符(manipulator),将它写入输出流时具有输出换行的效果,并刷新与设备相关联的缓冲区(buffer)。通过刷新缓冲区用户可立即看到写入到流中的输出。
我在调试以上代码时在45行(cout<<endl;)处设置断点,结果发现“43行(cout<<arr[i][j].first<<arr[i][j].second<<"";) 没有执行”,这就是因为43行末尾没有加endl,所以用户没有立即看到输出流中的数据。