LeetCode问题53：最大的连续子数组和

问题描述

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.

---

解题策略

分治法

将数组折半，分成左部分和右部分。具有最大和的连续子数组要么在左部分中，要么在右部分中，要么两个部分都有（横跨中间）。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return maxSub(nums, 0, nums.size());
    }
    int maxSub(vector<int>& nums, int s, int e) {
        if (s >= e)
            return INT_MIN;
        int leftSum, midSum, rightSum;
        int mid = (s+e)/2;
        int sum = 0;
        int t1 = INT_MIN, t2 = INT_MIN;
        for (int i = mid-1; i >= s; --i) {
            sum += nums[i];
            t1 = max(sum, t1);
        }
        sum = 0;
        for (int i = mid+1; i < e; ++i) {
            sum += nums[i];
            t2 = max(sum, t2);
        }
        midSum = nums[mid];
        if (t1 > 0)
            midSum += t1;
        if (t2 > 0)
            midSum += t2;
        leftSum = maxSub(nums, s, mid);
        rightSum = maxSub(nums, mid+1, e);
        return max(midSum, max(leftSum, rightSum));
    }
};

动态规划1

dp defines as: maxSubArray(int A[], int i), which means the maxSubArray for A[0:i ] which must has A[i] as the end element.

maxSubArray(A, i) = maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) : 0 + A[i];

class Solution {
public:
    int maxSubArray(vector<int>& nums) { 
        int n = nums.size();
        if(n == 0) return 0;
        int result = INT_MIN; 
        int pre = 0;
        for(int i = 0; i < n; ++i){
            pre = nums[i] + max(pre, 0);
            result = max(result, pre);
        }
        return result;
    }
};

---

1. 代码引用自LeetCode，作者不详 ↩