首先，什么是子串，什么是子序列？
子串必须连续，子序列可以不连续。 连续子序列就是子串
最大和最长也不一样，最大是求子序列加起来的数值最大，最长是这个子序列的长度最长。
最大连续子序列和 或者 最大连续子序列
其实可以叫做最大子串和
求一个数列的最大的连续子序列的和是多少，通常还要得到是从哪开始到哪结束。
例如，hdu1003 http://acm.hdu.edu.cn/showproblem.php?pid=1003
#include<stdio.h> #include<string.h> #include<string> #include<iostream> #include<algorithm> using namespace std; #define N 1234567 #define M 12 int n,a[N]; int main() { int T;cin>>T;int tt=1; while(T--) { cin>>n; for(int i=0;i<n;i++) scanf("%d",&a[i]); int sum=0,ma,temp=0,st=0,ed=0; ma=a[0]; for(int i=0;i<n;i++) { if(sum<0) { sum=a[i]; temp=i; } else { sum+=a[i]; } if(sum>ma) { st=temp; ma=sum; ed=i; } } printf("Case %d: ",tt++); printf("%d %d %d ",ma,st+1,ed+1); if(T)printf(" "); } return 0; }
最大上升子序列和
求一个数组的上升的子序列和最大是多少
hdu1087http://acm.hdu.edu.cn/showproblem.php?pid=1087
#include<stdio.h> #include<iostream> using namespace std; #define N 112345678 #define M 11234 #define INF 0x3f3f3f3f int a[N],d[N],n,m; int main() { while(cin>>n&&n) { for(int i=0;i<n;i++) { scanf("%d",&a[i]); d[i]=a[i]; } int ma=d[0]; for(int i=0;i<n;i++) { for(int j=0;j<i;j++) if(a[i]>a[j] && d[j]+a[i]>d[i]) { d[i]=d[j]+a[i]; ma=max(ma,d[i]); } } cout<<ma<<endl; } return 0; }
最长上升子序列（LIS）
入门题poj2553http://poj.org/problem?id=2533 只要求出最长数
#include<stdio.h> #include<iostream> using namespace std; #define N 112345678 int a[N],d[N],n; int main() { while(cin>>n) { for(int i = 0;i < n; i++) { scanf("%d",&a[i]); d[i]=1; } int ma=1; for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) { if(a[i] > a[j] && d[j] >= d[i]) d[i]=d[j]+1; } ma=max(ma,d[i]); } cout<<ma<<endl; } return 0; }
没找到题目，自己写了一下
#include<string.h> #include<iostream> #include<stdio.h> using namespace std; #define N 112345678 #define M 11234 #define INF 0x3f3f3f3f int n,m,a[N],b[N]; string s,t,p; int main() { while(cin>>s>>t) { int ma=0; memset(a,0,sizeof(a)); for(int i=0;i<s.length();i++) { for(int j=0;j<t.length();j++) { if(s[i]==t[j]) { if(j==0) a[j]=1; else a[j]=b[j-1]+1; } else a[j]=0; // printf("%d ",a[j]); // if(j==t.length()-1)printf(" "); if(a[j]>ma) { ma=a[j]; p=t.substr(j-ma+1,ma); } } for(int j=0;j<t.length();j++) b[j]=a[j]; } cout<<"最长公共子串长度: "<<ma<<endl; cout<<"公共子串: "<<p<<endl; } return 0; }
最长公共子序列（LCS）
poj1458 http://poj.org/problem?id=1458 这是最简单的，只要输出LCS的长度，不需要输出是什么
#include<string.h> #include<string> #include<stdio.h> #include<iostream> using namespace std; #define M 11234 #define INF 0x3f3f3f3f int d[M][M],n,m; string s1,s2; int main() { while(cin>>s1>>s2) { for(int i=1;i<=s1.length();i++) for(int j=1;j<=s2.length();j++) { if(s1[i-1]==s2[j-1]) d[i][j]=d[i-1][j-1]+1; else d[i][j] = max(d[i-1][j],d[i][j-1]); } cout<<d[s1.length()][s2.length()]<<endl; } return 0; }
如果poj1458 加上输出公共子序列（有多个输出任意一个即可），则代码如下
#include<string.h> #include<string> #include<stdio.h> #include<iostream> using namespace std; #define M 11234 #define INF 0x3f3f3f3f int d[M][M],path[M],n,m; string s1,s2; int main() { while(cin>>s1>>s2) { for(int i=1;i<=s1.length();i++) for(int j=1;j<=s2.length();j++) { if(s1[i-1]==s2[j-1]) d[i][j]=d[i-1][j-1]+1; else d[i][j] = max(d[i-1][j],d[i][j-1]); } cout<<d[s1.length()][s2.length()]<<endl; int i=s1.length(),j=s2.length(),k=0; while(d[i][j]) { if(s1[i-1]==s2[j-1]) { path[k++]=i-1; i--;j--; } else if(d[i][j]==d[i-1][j]) i--; else j--; } printf("路径："); for(int i=k-1;i>=0;i--) printf("%c", (char)s1[ path[i] ]); printf(" "); } return 0; }
如果要输出所有的最长公共子序列
（待研究）
hdu1503
最长上升公共子序列
zoj 2432
#include<algorithm> #include<string> #include<string.h> #include<stdio.h> #include<iostream> using namespace std; #define N 505 int a[N],l1,l2,b[N],ma,f[N][N]; int pre_i[N][N], pre_j[N][N], path[N], mj; void solve3() { memset(f, 0, sizeof(f) ); memset(pre_i, 0, sizeof(pre_i) ); memset(pre_j, 0, sizeof(pre_j) ); for(int i = 1; i <= l1; i++) { int ma1 = 0, i1 = 0, j1 = 0; for(int j = 1; j <= l2; j++) { f[i][j] = f[i-1][j]; pre_i[i][j] = i-1; pre_j[i][j] = j; if(a[i-1] > b[j-1] && f[i-1][j] > ma1) { ma1 = f[i-1][j]; i1 = i-1; j1 = j; } if(a[i-1] == b[j-1]) { f[i][j] = ma1 + 1; pre_i[i][j] = i1; pre_j[i][j] = j1; } } } ma = mj = -1; for(int j = 1; j <= l2; j++) if(f[l1][j] > ma) { ma = f[l1][j]; mj = j; } int i = l1, j = mj ,k = 0; while( f[i][j] ) { int x = pre_i[i][j], y = pre_j[i][j]; if(f[i][j] != f[x][y]) { path[k++] = b[j-1]; } i = x; j = y; } cout<<ma<<endl; for(i = k-1; i >= 0; i--) { printf("%d", path[i]); if(i > 0) printf(" "); else printf(" "); } } int main() { int T;cin>>T; while(T--) { scanf("%d", &l1); for(int i = 0; i < l1; i++) scanf("%d", &a[i]); scanf("%d", &l2); for(int i = 0; i < l2; i++) scanf("%d", &b[i]); solve3(); } return 0; } /* 99 5 1 4 2 5 -12 4 -12 1 2 4 9 3 5 1 6 7 9 1 5 13 6 4 6 13 9 13 5 */