[LeetCode]53.Maximum Subarray

【题目】

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array[−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray[4,−1,2,1]has the largest sum =6.

click to show more practice.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

【分析】

详细参考：编程之美之2.14 求数组的子数组之和的最大值

【代码】

/*********************************
*   日期：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;
}

【分析二】

如果将所给数组(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）。

【代码二】

    /*********************************
    *   日期：2015-02-03
    *   作者：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) {
            return Divide(A,0,n-1);
        }
    private:
        int Divide(int A[],int left,int right){
            if(left > right){
                return 0;
            }//if
            if(left == right){
                return A[left];
            }//if
            //
            int mid = left + (right - left) / 2;
            //1.跨越a和b之间的部分
            //1.1在a中的部分是a中包含右边界的最大子数组
            int sum = 0;
            int leftMax = A[mid];
            for(int i = mid;i >= left;--i){
                sum += A[i];
                leftMax = max(sum,leftMax);
            }//for
            //1.2在b中的部分是b中包含左边界的最大子数组
            sum = 0;
            int rightMax = A[mid+1];
            for(int i = mid+1;i <= right;++i){
                sum += A[i];
                rightMax = max(sum,rightMax);
            }//for
            // 前半部分最大和
            int aMax = Divide(A,left,mid);
            // 后半部分最大和
            int bMax = Divide(A,mid+1,right);
            // 跨越mid的最大和
            int cMax = leftMax + rightMax;
            return max(max(aMax,bMax),cMax);
        }
    };
    int main(){
        Solution solution;
        int n = 9;
        int A[] = {-2,1,-3,4,-1,2,1,-5,4};
        //int A[] = {-9,-2,-3,-5,-3};
        //int A[] = {0,-2,3,5,-1,2};
        int result = solution.maxSubArray(A,n);
        // 输出
        cout<<result<<endl;
        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;
        }
    };