【题目】

一个有N个整数元素的一维数组(A[0],A[1],A[2],...A[n-1]),这个数组中当然有很多子数组，那么子数组之和的最大值是多少？

该子数组是连续的。

我们先来明确一下题意：

（1）子数组意味着是连续的。

（2）题目只需要求和，并不需要返回子数组的具体位置。

（3）数组的元素是整数，所以数组可能包含正整数，负整数或者零。

举几个例子：

数组：[1,-2,3,5,-3,2]返回8 

数组：[0,-2,3,5,-1,2]返回9

数组：[-9,-2,-3,-5,-3]返回8

【解法一】

设Sum[i,...,j]为数组A中第i个元素到第j个元素的和(0<=i<=j<n),遍历所有的Sum[i,...,j]。

对每个整数对，我们都要计算x[i...j]的总和，并检验该总和是否大于迄今为止的最大总和。

/*********************************
*   日期：2014-5-19
*   作者：SJF0115
*   题目: 2.14 求数组的子数组之和的最大值
*   来源：编程之美
**********************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <limits.h>
using namespace std;

#define N 1001

int array[N];

int main(){
    int n,i,j,k,sum;
    //freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
    while(scanf("%d",&n) != EOF){
        //输入数据
        for(i = 0;i < n;i++){
            scanf("%d",&array[i]);
        }
        int maxSum = INT_MIN;
        // i 遍历数组起点 j 遍历数组终点
        for(i = 0;i < n;i++){
            for(j = i;j < n;j++){
                sum = 0;
                //遍历所有可能的Sum[i..j]
                for(k = i;k <= j;k++){
                    sum += array[k];
                }
                maxSum = max(maxSum,sum);
            }
        }
        printf("%d\n",maxSum);
    }
    return 0;
}

【解法二】

x[i...j]的总和与前面已经计算出的x[i...j-1]的总和密切相关，Sum[i..j] = Sum[i...j-1]+array[j] 则可以将上面算法中最后一个循环去掉，

避免重复计算，从而使算法得以改进。

时间复杂度为O（n^2）。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <limits.h>
using namespace std;

#define N 1001

int array[N];

int main(){
    int n,i,j,k,sum;
    //freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
    while(scanf("%d",&n) != EOF){
        //输入数据
        for(i = 0;i < n;i++){
            scanf("%d",&array[i]);
        }
        int maxSum = INT_MIN;
        // i 遍历数组起点 j 遍历数组终点
        for(i = 0;i < n;i++){
            sum = 0;
            for(j = i;j < n;j++){
                sum += array[j];
                maxSum = max(maxSum,sum);
            }
        }
        printf("%d\n",maxSum);
    }
    return 0;
}

【解法三】

通过访问外循环执行之前就以构建好的数据结构的方式在内循环中计算总和。

即常见的前缀和技巧。令Sumi=A0+A1+A2+…+Ai，规定Sum0=A0，则可以在O(1)时间内求出子序列的值：Ai+Ai+1+…+Aj=Sumj-Sumi-1。这样，时间复杂度降为O(n2)。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

#define N 1001

int array[N];
int sum[N];
int main(){
    int n,i,j;
    //freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
    while(scanf("%d",&n) != EOF){
        //输入数据
        for(i = 0;i < n;i++){
            scanf("%d",&array[i]);
            //计算前缀和
            if(i != 0){
                sum[i] = sum[i-1] + array[i];
            }
            else{
                sum[i] = array[i];
            }
        }
        int maxSum = sum[0];
        // i 遍历数组起点 j 遍历数组终点
        for(i = 0;i < n;i++){
            for(j = i+1;j < n;j++){
                maxSum = max(maxSum,sum[j] - sum[i]);
            }
        }
        printf("%d\n",maxSum);
    }
    return 0;
}

【解法四】 分治策略

如果将所给数组(A[0],...,A[n-1])分为长度相等的两段数组(A[0],...,A[n/2-1])和(A[n/2],...,A[n-1]),分别求出这两段数组各自最大子段和，则原数组(A[0],...,A[n-1])的最大子段和分为以下三种情况：
          a.(A[0],...,A[n-1])的最大子段和与(A[0],...,A[n/2-1])的最大子段和相同；
          b.(A[0],...,A[n-1])的最大子段和与(A[n/2],...,A[n-1])的最大子段和相同；
          c.(A[0],...,A[n-1])的最大子段跨过其中间两个元素A[n/2-1]到A[n/2].
对应a和b两个问题是规模减半的两个相同的子问题，可以用递归求得。
对于c,需要找到以A[n/2-1]结尾的和最大的一段数组和S1=(A[i],...,A[n/2-1])和以A[n/2]开始和最大的一段和S2=(A[n/2],...,A[j]),那么第三种情况的最大值为S1+S2。只需要对原数组进行一次遍历即可。

这其实是一种分治策略，时间复杂度为O（nlogn）。