53. Maximum Subarray 最大子数组

题目链接
tag:

• Easy;
• Dynamic Programming;
• Divide and Conquer;

question:
  Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

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

思路:
  设置两个辅助变量，累加子数组和cur_sum、最大子数组和max_sum。初始的累加子数组和cur_sum为数组的第一个元素，初始的最大子数组和max_sum为数组的第一个元素。更新cur_sum方法：如果cur_sum>0，则继续累加；否则用下一个元素值替换累加的子数组和。更新max_sum方法：如果cur_sum >max_sum，则用累加的子数组和替换最大的子数组和。

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int>& array)
        if (array.empty()) return 0;
        // 辅助变量
        int cur_sum = array[0];  // cur_sum为当前和
        int max_sum = array[0];  // max_sum为最大和
        // 遍历所有元素
        for (int i=1; i<array.size(); ++i) {
            // 更新cur_sum
            if (cur_sum <= 0)
                cur_sum = array[i];
            else
                cur_sum += array[i];
            }
            // 跟新max_sum
            if (cur_sum > max_sum)
                max_sum = cur_sum;
        }
        return max_sum;
    }
};

  题目还要求我们用分治法Divide and Conquer Approach来解，这个分治法的思想就类似于二分搜索法，我们需要把数组一分为二，分别找出左边和右边的最大子数组之和，然后还要从中间开始向左右分别扫描，求出的最大值分别和左右两边得出的最大值相比较取最大的那一个，代码如下：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.empty()) return 0;
        return helper(nums, 0, (int)nums.size() - 1);
    }
    int helper(vector<int>& nums, int left, int right) {
        if (left >= right) return nums[left];
        int mid = left + (right - left) / 2;
        int lmax = helper(nums, left, mid - 1);
        int rmax = helper(nums, mid + 1, right);
        int mmax = nums[mid], t = mmax;
        for (int i = mid - 1; i >= left; --i) {
            t += nums[i];
            mmax = max(mmax, t);
        }
        t = mmax;
        for (int i = mid + 1; i <= right; ++i) {
            t += nums[i];
            mmax = max(mmax, t);
        }
        return max(mmax, max(lmax, rmax));
    }
};