最大子序列和问题
本周学习陈越老师的数据结构课程时，约到最大子序列和的问题。趁着周末有空，把脑海中还有的记忆整理下。
最大子序列和问题：给定一个由n个整数组成成的序列{a1，a2，...，an}，求函数f（i，j）=max{0,σjk=iak}的最大值。
第一种方法可以用枚举法，把所有的可能的组合都遍历一遍。
#include <stdio.h>
#include <iostream>
using namespace std;
int maxsubsum(int a[], int n){
int i, j, k, sum, maxsum = 0;
for( i = 0; i<n; i++){//子序列左端
for( j = i; j<n; j++){//子序列右端
sum=0;//初始化子序列和
for (k= i; k<j; k++){
sum+=a[k];//求得子序列和
}
if(sum>maxsum){//对比子序列和
maxsum=sum;//更新子序列和
}
}
}
return maxsum;
}
int main(){
int n, i = 0;
scanf("%d\n",&n);//数组长度
int a[n];
for ( i= 0; i<n; i++){//输入数组
scanf("%d",&a[i]);
}
printf("\n%d",maxsubsum(a,n));
return 0;
}
把所有可能都求出来然后相加，时间复杂度为o(n3)。在该方法上改进，对于左端相同（即i相同)右端不同（即j不同）的子序列的和，只需要在前一项的结果加上当前的右端a[j]即可。
#include <stdio.h>
#include <iostream>
using namespace std;
int maxsubsum(int a[], int n){
int i, j, k, sum, maxsum = 0;
for( i = 0; i<n; i++){//子序列左端
sum=0;//初始化子序列和
for( j = i; j<n; j++){//子序列右端
sum+=a[j];//相同的i，不同j的子序列的和，只需要在上一次的结果上累加即可
}
if(sum>maxsum){//对比子序列和
maxsum=sum;//更新子序列和
}
}
return maxsum;
}
int main(){
int n, i = 0;
scanf("%d\n",&n);//数组长度
int a[n];
for ( i= 0; i<n; i++){//输入数组
scanf("%d",&a[i]);
}
printf("\n%d",maxsubsum(a,n));
return 0;
}
改进后，时间复杂度为o(n2)。
第二种方法，可以用分治法；分治法：把问题分解为小的子问题解决，然后把解决的子问题合并得出原问题的答案。再最大子序列问题中算法思路是：
（1）把原序列一份为二，分解为左右大小分别为（n/2）大小的序列；
（2）变为求解左右两个序列的最大子序列问题，和解跨越两个子序列边界的最大子序列问题；
（3）求解左右两个子序列值时，按（1）（2）步骤重复，直到不能再划分为二，此时，子序列为a[i]，为一个元素；
（4）把所有子问题答案整合，即为原问题的最大子序列答案。
#include <stdio.h>
#include <iostream>
using namespace std;
int max(int a, int b, int c){//求最大整数
int max=a;
if(b>max){
max=b;
}
if(c>max){
max=c;
}
return max;
}
int maxsubsum(int a[], int left, int right){
int maxleftsum, maxrightsum,
maxleftbordersum, maxrightbordersum,
leftbordersum, rightbordersum;
if(left == right)
if(a[left]>0)
return a[left];
else
return 0;
int center, i;
center = (left+right)/2;//分界线
maxleftsum = maxsubsum(a, left, center);
maxrightsum = maxsubsum(a, center+1, right);//递归求左右两边子列的最大子列和
maxleftbordersum = 0, leftbordersum=0;
for ( i = center; i>=left; i--){
leftbordersum+=a[i];
if(leftbordersum>maxleftbordersum){
maxleftbordersum=leftbordersum;
}
}//向左扫求跨边界的最大子列和
maxrightbordersum = 0, rightbordersum=0;
for ( i = center+1; i<=right; i++){
rightbordersum+=a[i];
if(rightbordersum>maxrightbordersum){
maxrightbordersum=rightbordersum;
}
}//向右扫求跨边界的最大子列和
return max(maxleftsum, maxrightsum, maxleftbordersum+maxrightbordersum);//返回左右子列，和跨边界子列中最大的子列和
}
int main(){
int n;
scanf("%d\n",&n);
int a[n];
for (int i= 0; i<n; i++){
scanf("%d",&a[i]);
}
int right = n-1, left=0;
printf("\n%d",maxsubsum(a,left,right));
system("pause");
return 0;
}
这个算法总的时间复杂度的递推公式：t(n)=2*t(n/2)+c*n; t(n/2)=2*(n/4)+c*(n/2).........t(1)=o(1) ;t(n)=2k*o(1)+c*kn, 2k=n; t(n)=o(n)+o(n*logn);该算法时间复杂度为n*logn。
第三种算法是在线处理法。该算法的思路是：
（1）先给最大子序列和初始化为0
（2）从左往右逐项累加求和；
（3）把（2）中逐项累加的和与已有的最大子序列和对比，若当前和比最大子序列和大，则把值赋予最大子序列；
（4）若当前和为负，则可以判断其与后面任何项相加，都会使其变小，因此，舍去前面的项，把当前和归0；
（5）重复（2）-（4）得到最大子列和。
#include <stdio.h>
#include <iostream>
using namespace std;
int maxsubsum(int a[], int n){
int i, maxsum = 0, sum = 0;//给maxsum设置一个小值
for (i = 0; i<n; i++ ){
sum += a[i]; //逐项相加
if(sum>maxsum){
maxsum = sum; //如果当前的子项的和大于maxsum,把当前子项的和sum代入
}
else if (sum<0){
sum = 0;//若当前子项和小于0，则归零从当前项开始重新累加
}
}
return maxsum;
}
int main(){
int n;
scanf("%d\n",&n);
int a[n];
for (int i= 0; i<n; i++){
scanf("%d",&a[i]);
}
printf("\n%d",maxsubsum(a,n));
system("pause");
return 0;
}
该算法时间复杂度为o(n)。但当整个序列都不为正数时，给出答案会是0，很明显是不正确的；因此可以做下改进，得到：
#include <stdio.h>
#include <iostream>
using namespace std;
int maxsubsum(int a[], int n){
int i, k = 0, maxsum = 0, sum = 0;//给maxsum初始化为0
for(i= 0; i<n; i++){ //判断整个序列是否都不大于0
if(a[i]>0){
k=1;
}
}
if(k){
for (i = 0; i<n; i++ ){
sum += a[i]; //逐项相加
if(sum>maxsum)
maxsum = sum; //如果当前的子项的和大于maxsum,把当前子项的和sum代入
else if (sum<0)
sum = 0;//若当前子项和小于0，则归零从当前项开始重新累加
}
}
else{
maxsum = a[0];
for (i = 0; i<n; i++ ){
if(a[i]>maxsum)
maxsum = a[i]; //当整个序列都不为正时，最大子序列也就是其序列元素中的最大值
}
}
return maxsum;
}
int main(){
int n;
scanf("%d\n",&n);
int a[n];
for (int i= 0; i<n; i++){
scanf("%d",&a[i]);
}
printf("\n%d",maxsubsum(a,n));
system("pause");
return 0;
}