编程之美之2.14 求数组的子数组之和的最大值

【题目】

一个有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;
}

时间复杂度为O（n^3）。程序运行速度很慢。

【解法二】

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中，要么在后半部分b中，要么跨越a和b之间的边界：
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。只需要对原数组进行一次遍历即可。在a中的部分是a中包含右边界的最大子数组，在b中的部分是b中包含左边界的最大子数组。

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

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

#define N 1001

int array[N];

int MaxSubsequence(int L,int R){
    int i,j;
    //0个元素
    if(L > R){
        return 0;
    }
    //1个元素
    if(L == R){
        return array[L];
    }
    int mid = (L + R) / 2;
    //跨越a和b之间的部分
    //在a中的部分是a中包含右边界的最大子数组
    int sum = 0;
    int leftMax = array[mid];
    for(i = mid;i >= L;i--){
        sum += array[i];
        leftMax = max(leftMax,sum);
    }
    //在b中的部分是b中包含左边界的最大子数组
    sum = 0;
    int rightMax = array[mid+1];
    for(i = mid+1;i <= R;i++){
        sum += array[i];
        rightMax = max(rightMax,sum);
    }
    //递归调用
    //跨越a和b
    int maxSum = rightMax+leftMax;
    //整个在a中
    maxSum = max(maxSum,MaxSubsequence(L,mid));
    //整个在b中
    maxSum = max(maxSum,MaxSubsequence(mid+1,R));
    return maxSum;
}

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]);
        }
        int maxSum = MaxSubsequence(0,n-1);
        printf("%d\n",maxSum);
    }
    return 0;
}

【解法五】

利用动态规划做题。

只遍历数组一遍，当从头到尾部遍历数组A， 遇到一个数有两种选择 （1）加入之前subArray （2）自己另起一个subArray

设状态S[i], 表示以A[i]结尾的最大连续子序列和，状态转移方程如下:

S[i] = max(S[i-1] + A[i],A[i])

时间复杂度：O(n) 空间复杂度：O(n)

【代码五】

    /*--------------------------------------------
    *   日期：2015-02-03
    *   作者：SJF0115
    *   题目: 53.Maximum Subarray
    *   网址：https://oj.leetcode.com/problems/maximum-subarray/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    -----------------------------------------------*/
    class Solution {
    public:
        int maxSubArray(int A[], int n) {
            int S[n];
            int maxSum = A[0];
            S[0] = A[0];
            // 动态规划
            for(int i = 1;i < n;i++){
                S[i] = max(S[i-1] + A[i],A[i]);
                if(S[i] > maxSum){
                    maxSum = S[i];
                }//if
            }//for
            return maxSum;
        }
    };

【解法六】

对前一个方法继续优化，从状态转移方程上S【i】只与S【i-1】有关，与其他都无关，因此可以用一个变量来记住前一个的最大连续数组和就可以了。

这样就可以节省空间了。

时间复杂度：O(n) 空间复杂度：O(1)

【代码六】

    /*--------------------------------------------
    *   日期：2015-02-03
    *   作者：SJF0115
    *   题目: 53.Maximum Subarray
    *   网址：https://oj.leetcode.com/problems/maximum-subarray/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    -----------------------------------------------*/
    class Solution {
    public:
        int maxSubArray(int A[], int n) {
            int maxSum = A[0];
            // sum 记住前一个的最大连续数组和
            int sum = 0;
            // 动态规划
            for(int i = 0;i < n;i++){
                sum += A[i];
                sum = max(sum,A[i]);
                if(sum > maxSum){
                    maxSum = sum;
                }//if
            }//for
            return maxSum;
        }
    };

【解法七】

时间复杂度：O(n) 空间复杂度：O(1)

/*********************************
*   日期：2015-01-27
*   作者：SJF0115
*   题目: 53.Maximum Subarray
*   网址：https://oj.leetcode.com/problems/maximum-subarray/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
#include <climits>
using namespace std;

class Solution {
public:
    int maxSubArray(int A[], int n) {
        if(n <= 0){
            return 0;
        }//if
        // 最大和
        int max = A[0];
        // 当前最大和
        int cur = 0;
        for(int i = 0;i < n;++i){
            // 一旦当前最大和小于0就重置为0,一个负数只能使最大和变小
            if(cur < 0){
                cur = 0;
            }//if
            cur += A[i];
            if(cur > max){
                max = cur;
            }//if
        }//for
        return max;
    }
};
int main(){
    Solution solution;
    int n = 9;
    int A[] = {-2,1,-3,4,-1,2,1,-5,4};
    int result = solution.maxSubArray(A,n);
    // 输出
    cout<<result<<endl;
    return 0;
}

【相似题目】

UVA之1121 - Subsequence

[LeetCode]53.Maximum Subarray