最大连续子序列和（4种算法）

问题：
已知 一个整数序列a[n]：n个整数（有正负）
求 在这个序列的所有子序列（连续）中，最大的和是多少？

注意：
以下代码都要求最大和 【可为负数】，若要求最大和 【非负】，只需最后判断一下即可

1 算法1

#include<cstdio>

using namespace std;

// 整数序列a[n]
int max_subseq_sum1(int a[], int n){
    int max_sum=a[0];				// 所有 子序列中的最大和
    int this_sum;					// 当前 子序列的和
    int i,j,k;
    for(i=0; i<n; i++){         	// 以a[i]开头的所有子序列
        for(int j=i; j<n; j++){  	// 子序列： a[i] ~ a[j]
            this_sum = 0;
            for(k=i; k<=j; k++){
                this_sum += a[k];
            }
			//
            if(this_sum > max_sum){
                max_sum = this_sum;
            }
        }
    }
    return max_sum;
}

int main(){
    int a[5] = {-1, 10, 4, -10, 3};
    int max_sum;
    max_sum = max_subseq_sum1(a, 5);
    printf("%d\n", max_sum);
    return 0;
}

$T(n) = O(n^{3})$T(n)=O(n3)

---

2 算法2

// 整数序列a[n]
int max_subseq_sum2(int a[], int n){
    int max_sum=a[0];				// 所有 子序列中的最大和
    int this_sum;					// 当前 子序列的和
    int i,j;
    for(i=0; i<n; i++){         	// 以a[i]开头的所有子序列
        this_sum = 0;
        for(int j=i; j<n; j++){ 	// 子序列： a[i] ~ a[j]
            this_sum += a[j];
			//
            if(this_sum > max_sum){
                max_sum = this_sum;
            }
        }
    }
    return max_sum;
}

$T(n) = O(n^{2})$T(n)=O(n2)

---

3 算法3（分治）

//分治法求 a[left] ~ a[right]的最大子列和
int divide_conquer(int a[], int left, int right){
    int max_left_sum, max_right_sum;        // 左右子问题的解（最大和）
    int center;                             // 中间线
    int max_border_sum;                     // 跨分界线的解（最大和）
    int max_left_border_sum, max_right_border_sum;         // 跨分界线向左右扫描的最大和
    int this_left_border_sum, this_right_border_sum;

    /*
    递归终止
    */
    if( left == right )  {                  // 子列只有1个数字
        return a[left];
    }

    /*
    分
    */
    center = (left + right) / 2;
    // 1. 中间线左边 的最大子列和
    max_left_sum = divide_conquer(a, left, center);
    // 2. 中间线右边 的最大子列和
    max_right_sum = divide_conquer(a, center+1, right);
    // 3.跨中间线 的最大子列和
    max_left_border_sum=a[center];
    this_left_border_sum=0;
    for(int i=center; i>=left; i--){  //从中间线开始，向左扫描
        this_left_border_sum += a[i];
        if(this_left_border_sum > max_left_border_sum){
            max_left_border_sum = this_left_border_sum;
        }
    }
    max_right_border_sum=a[center+1];
    this_right_border_sum=0;
    for(int i=center+1; i<=right; i++){  //从中间线开始，向右扫描
        this_right_border_sum += a[i];
        if(this_right_border_sum > max_right_border_sum){
            max_right_border_sum = this_right_border_sum;
        }
    }
    max_border_sum = max_left_border_sum + max_right_border_sum;

    /*
    治
    */
    return max(max(max_left_sum, max_right_sum), max_border_sum);
}


// 整数序列a[n]
int max_subseq_sum3(int a[], int n){
    return divide_conquer(a, 0, n-1);
}

$T(n) = O(nlogn)$T(n)=O(nlogn)

---

4 算法4（在线处理，最快）

在线：每输入一个数据就进行即时处理，在任何一个地方中止输入，算法都能正确给出当前的解。

// 整数序列a[n]
int max_subseq_sum4(int a[], int n){
    int max_sum=a[0];					// 所有 子序列中的最大和
    int this_sum=0;					// 当前 子序列的和
    int i;
    for(i=0; i<n; i++){         	// 以a[i]开头的所有子序列
        this_sum += a[i];           // 向右累加
        //
        if(this_sum > max_sum){
            max_sum = this_sum;
        }
        if(this_sum <0){            // 当前子序列和为负
            this_sum=0;             // 则不可能使向右累加的和增大，故抛弃
        }
    }
    return max_sum;
}

$T(n) = O(n)$T(n)=O(n)