算法之最长子序列之和.docVIP

算法之最长子序列之和 使用分治法、蛮力法和动态规划法分别求得最大公共子序列。 最长子序列之和问题，是指在一个集合中的所有子集，要求找出自己中的最长子集的和的问题。子集在算法中和子序列是一个道理。 例如集合中包含{1，2，3，4，5}，那么它的子集有{1}，{1，2}，{1，2，3}等等，求出这些子集中最长的和就是算法中的关键，自己想想，其实最长子序列就是集合本身，但是要利用算法求解，使用分治法、蛮力法和动态规划求，这才是关键，不是单纯的加加减减。 程序实现及C++代码 一、分治法求解 #includeiostream using namespace std; int MaxSum(int a[],int left,int right) { int sum=0; if (left==right) { //如果序列长度为1，直接求解 if (a[left]0)sum=a[left]; else sum=0; } else { int center=(left+right)/2; int leftsum=MaxSum(a,left,center); int rightsum=MaxSum(a,center+1,right); int s1=0; int lefts=0; for(int i=center;i=left;i--) { lefts+=a[i]; if(leftss1) s1=lefts; } int s2=0; int rights=0; for(int j=center+1;j=right;j++) { rights+=a[j]; if(rightss2) s2=rights; } sum=s1+s2; if(sumleftsum)sum=leftsum; //合并，在sum、leftsum和rightsum中取较大者 if(sumrightsum)sum=rightsum; } return sum; } void main() { int n,a[100],m,maxsum; cout请输入整数序列的元素个数n:endl; cinn; cout请输入各元素的值(一共n个):endl; for(m=1;m=n;m++) cina[m]; maxsum=MaxSum(a,1,n); cout整数序列的最大子段和是：maxsumendl; } 运行结果 二、蛮力法求解 #include iostream using namespace std; void main() { int n,j,i,sum,max=0; int a[100],b[100]; cout输入序列元素个数:; cinn; cout输入序列元素:; for(i=1;i=n;i++) cina[i]; for(j=1;j=n;j++) { b[j]=0; sum=0; for(i=j;i=n;i++) { sum=sum+a[i]; if(sumb[j]) { b[j]=sum; } continue; } } for(j=1;j=n;j++) { if(b[j]max) max=b[j]; } cout最大子串和为:maxendl; } 运行结果： 动态规划法 #include iostream using namespace std; void maxsum(); void main() { maxsum(); } void maxsum() { int i,j,n,k=1; int max=0,sum=0; int a[100],b[100]; cout输入序列元素个数:; cinn; cout输入元素:endl; for(i=1;i=n;i++) { cina[i]; } b[1]=a[1]; for(i=2;i=n;i++) { if(b[i-1]=0) b[i]=a[i]; else b[i]=b[i-1]+a[i]; } for(j=1;j=n;j++) { if(maxb[j]) { max=b[j]; } } cout最大子段和为:maxendl; } 运行结果