- 浏览: 21243 次
- 性别:
- 来自: 南京
最新评论
最大子序列
最大子序列是要找出由数组成的一维数组中和最大的连续子序列。比如{5,-3,4,2}的最大子序列就是 {5,-3,4,2},它的和是8,达到最大;而 {5,-6,4,2}的最大子序列是{4,2},它的和是6。你已经看出来了,找最大子序列的方法很简单,只要前i项的和还没有小于0那么子序列就一直向后扩展,否则丢弃之前的子序列开始新的子序列,同时我们要记下各个子序列的和,最后找到和最大的子序列。
代码如下:
#include<iostream>
using namespace std;
int MaxSubSeq(const int *arr,int len,int *start,int *end){
int max=0; //记录目前找到的最大子序列的和
int sum=0; //记录当前子序列的和
int begin=0,finish=0; //记录当前子序列的起始下标
*start=begin;*end=finish; //记录最长子序列的起始下标
for(int i=0;i<len;i++){
sum+=arr[i];
finish=i;
if(sum>max){
max=sum;
*end=finish;
*start=begin;
}
if(sum<=0){
sum=0;
begin=i+1;
}
}
return max;
}
int main(){
int arr[6]={5,-3,-2,12,9,-1};
int start,end;
int max=MaxSubSeq(arr,6,&start,&end);
cout<<"The MaxSubSeq is from position "<<start<<"to position "<<end<<"."<<endl;
cout<<"Sum of MaSubSeq: "<<max<<endl;
return 0;
}
最长公共子串(LCS)
找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。其实这又是一个序贯决策问题,可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢?直接举个例子吧:"bab"和"caba"(当然我们现在一眼就可以看出来最长公共子串是"ba"或"ab")
b a b
c 0 0 0
a 0 1 0
b 1 0 1
a 0 1 0
我们看矩阵的斜对角线最长的那个就能找出最长公共子串。
不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事,下面改进:当要在矩阵是填1时让它等于其左上角元素加1。
b a b
c 0 0 0
a 0 1 0
b 1 0 2
a 0 2 0
这样矩阵中的最大元素就是 最长公共子串的长度。
在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了,所以实际上在程序中可以用一维数组来代替这个矩阵。
代码如下:
#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); //当前行
int ylen=str2.size(); //纵向长度
int maxele=0; //矩阵元素中的最大值
int pos=0; //矩阵元素最大值出现在第几列
for(int i=0;i<ylen;i++){
string s=str2.substr(i,1);
arr.assign(xlen,0); //数组清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;
}
最长公共子序列
最长公共子序列与最长公共子串的区别在于最长公共子序列不要求在原字符串中是连续的,比如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)
举个例子:
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
填写最后一个数字时,它应该是下面三个的最大者:
(1)上边的数字2
(2)左边的数字2
(3)左上角的数字2+1=3,因为此时C1==C2
所以最终结果是3。
在填写过程中我们还是记录下当前单元格的数字来自于哪个单元格,以方便最后我们回溯找出最长公共子串。有时候左上、左、上三者中有多个同时达到最大,那么任取其中之一,但是在整个过程中你必须遵循固定的优先标准。在我的代码中优先级别是左上>左>上。
下图给出了回溯法找出LCS的过程:
奉上代码:
01
#include<iostream>
02
#include<cstring>
03
#include<stack>
04
#include<utility>
05
#define LEFTUP 0
06
#define LEFT 1
07
#define UP 2
08
using namespace std;
09
int Max(int a,int b,int c,int *max){ //找最大者时a的优先级别最高,c的最低.最大值保存在*max中
10
int res=0; //res记录来自于哪个单元格
11
*max=a;
12
if(b>*max){
13
*max=b;
14
res=1;
15
}
16
if(c>*max){
17
*max=c;
18
res=2;
19
}
20
return res;
21
}
22
//调用此函数时请注意把较长的字符串赋给str1,这主要是为了在回溯最长子序列时节省时间。如果没有把较长的字符串赋给str1不影响程序的正确执行。
23
string LCS(const string &str1,const string &str2){
24
int xlen=str1.size(); //横向长度
25
int ylen=str2.size(); //纵向长度
26
if(xlen==0||ylen==0) //str1和str2中只要有一个为空,则返回空
27
return "";
28
pair<int,int> arr[ylen+1][xlen+1]; //构造pair二维数组,first记录数据,second记录来源
29
for(int i=0;i<=xlen;i++) //首行清0
30
arr[0][i].first=0;
31
for(int j=0;j<=ylen;j++) //首列清0
32
arr[j][0].first=0;
33
for(int i=1;i<=ylen;i++){
34
char s=str2.at(i-1);
35
for(int j=1;j<=xlen;j++){
36
int leftup=arr[i-1][j-1].first;
37
int left=arr[i][j-1].first;
38
int up=arr[i-1][j].first;
39
if(str1.at(j-1)==s) //C1==C2
40
leftup++;
41
int max;
42
arr[i][j].second=Max(leftup,left,up,&arr[i][j].first);
43
// cout<<arr[i][j].first<<arr[i][j].second<<" ";
44
}
45
// cout<<endl;
46
} /*矩阵构造完毕*/
47
//回溯找出最长公共子序列
48
stack<int> st;
49
int i=ylen,j=xlen;
50
while(!(i==0&&j==0)){
51
if(arr[i][j].second==LEFTUP){
52
if(arr[i][j].first==arr[i-1][j-1].first+1)
53
st.push(i);
54
--i;
55
--j;
56
}
57
else if(arr[i][j].second==LEFT){
58
--j;
59
}
60
else if(arr[i][j].second==UP){
61
--i;
62
}
63
}
64
string res="";
65
while(!st.empty()){
66
int index=st.top()-1;
67
res.append(str2.substr(index,1));
68
st.pop();
69
}
70
return res;
71
}
72
int main(){
73
string str1="GCCCTAGCG";
74
string str2="GCGCAATG";
75
string lcs=LCS(str1,str2);
76
cout<<lcs<<endl;
77
return 0;
78
}
下面给一个Java版本
01
public static <E> List<E> longestCommonSubsequence(E[] s1,E[] s2){
02
int[][] num=new int[s1.length+1][s2.length+1];
03
for(int i=1;i<s1.length;i++){
04
for(int j=1;j<s2.length;j++){
05
if(s1[i-1].equals(s2[j-1])){
06
num[i][j]=1+num[i-1][j-1];
07
}
08
else{
09
num[i][j]=Math.max(num[i-1][j],num[i][j-1]);
10
}
11
}
12
}
13
System.out.println("lenght of LCS= "+num[s1.length][s2.length]);
14
int s1position=s1.length,s2position=s2.length;
15
List<E> result=new LinkedList<E>();
16
while(s1position!=0 && s2position!=0){
17
if(s1[s1position-1].equals(s2[s2position-1])){
18
result.add(s1[s1position-1]);
19
s1position--;
20
s2position--;
21
}
22
else if(num[s1position][s2position-1]>=num[s1position-1][s2position]){
23
s2position--;
24
}
25
else{
26
s1position--;
27
}
28
}
29
Collections.reverse(result);
30
return result;
31
}
std::endl是一个特殊值,称为操纵符(manipulator),将它写入输出流时具有输出换行的效果,并刷新与设备相关联的缓冲区(buffer)。通过刷新缓冲区用户可立即看到写入到流中的输出。
我在调试以上代码时在45行(cout<<endl;)处设置断点,结果发现“43行(cout<<arr[i][j].first<<arr[i][j].second<<" ";) 没有执行”,这就是因为43行末尾没有加endl,所以用户没有立即看到输出流中的数据。
最大子序列是要找出由数组成的一维数组中和最大的连续子序列。比如{5,-3,4,2}的最大子序列就是 {5,-3,4,2},它的和是8,达到最大;而 {5,-6,4,2}的最大子序列是{4,2},它的和是6。你已经看出来了,找最大子序列的方法很简单,只要前i项的和还没有小于0那么子序列就一直向后扩展,否则丢弃之前的子序列开始新的子序列,同时我们要记下各个子序列的和,最后找到和最大的子序列。
代码如下:
#include<iostream>
using namespace std;
int MaxSubSeq(const int *arr,int len,int *start,int *end){
int max=0; //记录目前找到的最大子序列的和
int sum=0; //记录当前子序列的和
int begin=0,finish=0; //记录当前子序列的起始下标
*start=begin;*end=finish; //记录最长子序列的起始下标
for(int i=0;i<len;i++){
sum+=arr[i];
finish=i;
if(sum>max){
max=sum;
*end=finish;
*start=begin;
}
if(sum<=0){
sum=0;
begin=i+1;
}
}
return max;
}
int main(){
int arr[6]={5,-3,-2,12,9,-1};
int start,end;
int max=MaxSubSeq(arr,6,&start,&end);
cout<<"The MaxSubSeq is from position "<<start<<"to position "<<end<<"."<<endl;
cout<<"Sum of MaSubSeq: "<<max<<endl;
return 0;
}
最长公共子串(LCS)
找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。其实这又是一个序贯决策问题,可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢?直接举个例子吧:"bab"和"caba"(当然我们现在一眼就可以看出来最长公共子串是"ba"或"ab")
b a b
c 0 0 0
a 0 1 0
b 1 0 1
a 0 1 0
我们看矩阵的斜对角线最长的那个就能找出最长公共子串。
不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事,下面改进:当要在矩阵是填1时让它等于其左上角元素加1。
b a b
c 0 0 0
a 0 1 0
b 1 0 2
a 0 2 0
这样矩阵中的最大元素就是 最长公共子串的长度。
在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了,所以实际上在程序中可以用一维数组来代替这个矩阵。
代码如下:
#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); //当前行
int ylen=str2.size(); //纵向长度
int maxele=0; //矩阵元素中的最大值
int pos=0; //矩阵元素最大值出现在第几列
for(int i=0;i<ylen;i++){
string s=str2.substr(i,1);
arr.assign(xlen,0); //数组清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;
}
最长公共子序列
最长公共子序列与最长公共子串的区别在于最长公共子序列不要求在原字符串中是连续的,比如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)
举个例子:
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
填写最后一个数字时,它应该是下面三个的最大者:
(1)上边的数字2
(2)左边的数字2
(3)左上角的数字2+1=3,因为此时C1==C2
所以最终结果是3。
在填写过程中我们还是记录下当前单元格的数字来自于哪个单元格,以方便最后我们回溯找出最长公共子串。有时候左上、左、上三者中有多个同时达到最大,那么任取其中之一,但是在整个过程中你必须遵循固定的优先标准。在我的代码中优先级别是左上>左>上。
下图给出了回溯法找出LCS的过程:
奉上代码:
01
#include<iostream>
02
#include<cstring>
03
#include<stack>
04
#include<utility>
05
#define LEFTUP 0
06
#define LEFT 1
07
#define UP 2
08
using namespace std;
09
int Max(int a,int b,int c,int *max){ //找最大者时a的优先级别最高,c的最低.最大值保存在*max中
10
int res=0; //res记录来自于哪个单元格
11
*max=a;
12
if(b>*max){
13
*max=b;
14
res=1;
15
}
16
if(c>*max){
17
*max=c;
18
res=2;
19
}
20
return res;
21
}
22
//调用此函数时请注意把较长的字符串赋给str1,这主要是为了在回溯最长子序列时节省时间。如果没有把较长的字符串赋给str1不影响程序的正确执行。
23
string LCS(const string &str1,const string &str2){
24
int xlen=str1.size(); //横向长度
25
int ylen=str2.size(); //纵向长度
26
if(xlen==0||ylen==0) //str1和str2中只要有一个为空,则返回空
27
return "";
28
pair<int,int> arr[ylen+1][xlen+1]; //构造pair二维数组,first记录数据,second记录来源
29
for(int i=0;i<=xlen;i++) //首行清0
30
arr[0][i].first=0;
31
for(int j=0;j<=ylen;j++) //首列清0
32
arr[j][0].first=0;
33
for(int i=1;i<=ylen;i++){
34
char s=str2.at(i-1);
35
for(int j=1;j<=xlen;j++){
36
int leftup=arr[i-1][j-1].first;
37
int left=arr[i][j-1].first;
38
int up=arr[i-1][j].first;
39
if(str1.at(j-1)==s) //C1==C2
40
leftup++;
41
int max;
42
arr[i][j].second=Max(leftup,left,up,&arr[i][j].first);
43
// cout<<arr[i][j].first<<arr[i][j].second<<" ";
44
}
45
// cout<<endl;
46
} /*矩阵构造完毕*/
47
//回溯找出最长公共子序列
48
stack<int> st;
49
int i=ylen,j=xlen;
50
while(!(i==0&&j==0)){
51
if(arr[i][j].second==LEFTUP){
52
if(arr[i][j].first==arr[i-1][j-1].first+1)
53
st.push(i);
54
--i;
55
--j;
56
}
57
else if(arr[i][j].second==LEFT){
58
--j;
59
}
60
else if(arr[i][j].second==UP){
61
--i;
62
}
63
}
64
string res="";
65
while(!st.empty()){
66
int index=st.top()-1;
67
res.append(str2.substr(index,1));
68
st.pop();
69
}
70
return res;
71
}
72
int main(){
73
string str1="GCCCTAGCG";
74
string str2="GCGCAATG";
75
string lcs=LCS(str1,str2);
76
cout<<lcs<<endl;
77
return 0;
78
}
下面给一个Java版本
01
public static <E> List<E> longestCommonSubsequence(E[] s1,E[] s2){
02
int[][] num=new int[s1.length+1][s2.length+1];
03
for(int i=1;i<s1.length;i++){
04
for(int j=1;j<s2.length;j++){
05
if(s1[i-1].equals(s2[j-1])){
06
num[i][j]=1+num[i-1][j-1];
07
}
08
else{
09
num[i][j]=Math.max(num[i-1][j],num[i][j-1]);
10
}
11
}
12
}
13
System.out.println("lenght of LCS= "+num[s1.length][s2.length]);
14
int s1position=s1.length,s2position=s2.length;
15
List<E> result=new LinkedList<E>();
16
while(s1position!=0 && s2position!=0){
17
if(s1[s1position-1].equals(s2[s2position-1])){
18
result.add(s1[s1position-1]);
19
s1position--;
20
s2position--;
21
}
22
else if(num[s1position][s2position-1]>=num[s1position-1][s2position]){
23
s2position--;
24
}
25
else{
26
s1position--;
27
}
28
}
29
Collections.reverse(result);
30
return result;
31
}
std::endl是一个特殊值,称为操纵符(manipulator),将它写入输出流时具有输出换行的效果,并刷新与设备相关联的缓冲区(buffer)。通过刷新缓冲区用户可立即看到写入到流中的输出。
我在调试以上代码时在45行(cout<<endl;)处设置断点,结果发现“43行(cout<<arr[i][j].first<<arr[i][j].second<<" ";) 没有执行”,这就是因为43行末尾没有加endl,所以用户没有立即看到输出流中的数据。
发表评论
-
KMP快速字符串查找算法
2011-08-25 19:29 640在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
求解最大公约数问题
2011-08-25 19:27 661最大公因数,又称最大公约数。是指 [n(≧2)个自然数 a1, ... -
堆排序(Heap Sort)算法学习
2011-08-25 19:26 1058在程序设计相关领域, ... -
整数拆分问题的动态规划解法
2011-08-25 19:26 3034输入n,和k,问将n用1到k这k个数字进行拆分,有多少种拆分方 ... -
背包问题介绍与分析
2011-08-25 19:24 1001背包问题是在1978年由Merkel和Hellman提出的。它 ... -
求平方根sqrt()函数的底层算法效率问题
2011-08-25 19:23 1264我们平时经常会有一些数据运算的操作,需要调用sqrt,exp, ... -
面试中常见的一些算法问题
2011-08-25 19:22 672Problem 1 : Is it a loop ? ( ... -
各种排序算法的C++实现与性能比较
2011-08-25 19:21 890排序是计算机算法中非常重要的一项,而排序算法又有不少实现方法, ... -
背包问题之硬币找零问题
2011-08-25 19:19 1129设有6 种不同面值的硬 ... -
求能被1到20的数整除的最小正整数
2011-08-25 19:18 1337求能被1到20的数整除的最小正整数。最直觉的方法是求1到20这 ... -
买书折扣最优惠问题解法
2011-08-25 19:17 720题目:在节假日的时候 ... -
二叉树中的最近公共祖先问题
2011-08-25 19:16 1293题目:要求寻找二叉树中两个节点的最近的公共祖先,并将其返回。 ... -
判断一个整数是否是2的N次方
2011-08-25 19:04 1789题目:给定一个整数num,判断这个整数是否是2的N次方。比如, ... -
字符串逆序的算法汇总
2011-08-25 19:01 1034很早就准备写一个字符串系列的面试题,本来已经写好了,大概有十几 ... -
计算从1到N中1的出现次数
2011-08-25 18:59 574给定一个十进制整数N, ... -
KMP快速字符串查找算法
2011-08-25 18:57 939在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
快速排序的递归实现
2011-08-25 18:54 728快速排序是对冒泡排序的一种改进。它的基本思想是:通过一次排序将 ... -
数字1亿里面有多少个1呢
2011-08-25 18:52 710乍看这题真够唬人的,群里看到这个题目后争先恐后的说看法。最简单 ... -
一道关于男女比例的面试题
2011-08-25 16:56 1016阿里巴巴的一道面试题:说澳大利亚的父母喜欢女孩,如果生出来的第 ...
相关推荐
求解最大子序列、最长递增子序列、最长公共子串、最长公共子序列. http://blog.csdn.net/ssuchange/article/details/17341693
2010.09.07 用分治法求解最大子序列问题。...《数据结构与算法分析 C++描述》p42最大子序列问题的递归方法代码 2010.09.07 vector a的内容: 4 -3 5 -2 -1 2 6 -2 最大子序列和是:11 请按任意键继续. . .
求最大子序列和的四个算法,通过对比,可以了解算法时间计算
最大子序列求和
常数时间实现寻找整数序列的最大子序列之和,内附输入格式说明
C 最大子序列问题的几中算法-分治-联机算法
最大子序列求和 c语言
利用C/C++语言解决最大子列和问题,在线处理-超简单的算法
最大子序列和问题,一个整形数组序列求一个不变顺序的相加最大和子序列。
最大子序列.pdf
C++算法_最大子序列和.zip
最大子序列和问题(Maximum Subarray Sum Problem)是求解一个数组中连续子数组的和的最大值的问题。
动态规划算法:最大子序列问题
最大子序列问题算法分析.doc
最大子序列算法[整理].pdf
cout整数序列最大子段和是:"; } void main(){ int n,a[100],m,maxsum; cout请输入整数序列的元素个数n"; cin>>n; cout请输入各元素的值:"; for(m=0;m;m++) cin>>a[m]; Maxsum(n,a); }
在第五章中更是对动态规划常见的一些体型进行了总结整理,包括“最长公共子序列,最长公共子串,背包,最大子数组和”;最后summary总结整理了链表常见的问题包括“链表是否有环,链表环的入口,是否相交,排序等”...
示例 2:输出:1示例 3:输出:0示例 4:输出:-1示例 5:输出:-100000思路:动态规划,对数组进行遍历,当前最大子序列和为sum, 结果为ans/
最长的公共子序列 最长的公共子字符串 最长递增子序列 最长递增子序列 O(Nlogn) 最长的子阵列 矩阵链顺序 最大非邻和 最大乘积子阵列 最大子数组 最大和连续子序列 底部的最小距离 最小硬币兑换 最低...
例如: 序列(-2,11,-4,13,-5,-2)的最大子序列和为20序列; (-6,2,4,-7,5,3,2,-1,6,-9,10,-2)的最大子序列和为16。 3.用分治策略求众数问题 问题描述:给定含有n个元素的多重集合S,每个元素在...