最大子序列和问题

　　本周学习陈越老师的数据结构课程时，约到最大子序列和的问题。趁着周末有空，把脑海中还有的记忆整理下。

　　最大子序列和问题：给定一个由n个整数组成成的序列{a₁，a₂，...，a_n}，求函数f（i，j）=max{0,σ^j_k=ia_k}的最大值。

　　第一种方法可以用枚举法，把所有的可能的组合都遍历一遍。

#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(n³)。在该方法上改进，对于左端相同（即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(n²)。

　　第二种方法，可以用分治法；分治法：把问题分解为小的子问题解决，然后把解决的子问题合并得出原问题的答案。再最大子序列问题中算法思路是：

　　（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)=2^k*o(1)+c*kn, 2^k=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;
}