LeetCodeDay21 —— 最大子序和

53. 最大子序和

描述

• 给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例

  输入: [-2,1,-3,4,-1,2,1,-5,4],
  输出: 6
  解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶

• 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

思路

1. 一开始被O(n)时间迷惑了，并不是要求一遍遍历就出结果，两遍遍历也是O(n)的时间复杂度。
2. 优先计算出每个以A[i]结尾的子数组的最大子序和，最后查一遍表，答案就出来了。
3. 可以在遍历的过程中用一个变量保存当前最大值，这样就只用遍历一遍了。
4. 状态方程为 Sum(i) = max(Sum(i-1) + A[i], A[i])
5. 分治思路：将数组均分为两个部分，那么最大子数组会存在于
   左侧数组的最大子数组
   右侧数组的最大子数组
   左侧数组的以右侧边界为边界的最大子数组+右侧数组的以左侧边界为边界的最大子数组
   (参考)

class Solution_53_01 {
 public:
  int maxSubArray(vector<int>& nums) {
    if (nums.size() == 0) return 0;
    int maxVal = nums[0];
    int sumi = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
      sumi = (sumi + nums[i] > nums[i]) ? sumi + nums[i] : nums[i];
      maxVal = sumi > maxVal ? sumi : maxVal;
    }
    return maxVal;
  }
};

class Solution_53_02 {
 public:
  int maxSubArray(vector<int>& nums) {
    if (nums.size() == 0) return 0;
    if (nums.size() == 1) return nums[0];

    vector<int> left(nums.begin(), nums.begin() + nums.size() / 2);
    int l = maxSubArray(left);

    int l_mid = left[left.size() - 1];
    int l_mid_max = l_mid;
    for (int i = left.size() - 2; i >= 0; --i) {
      l_mid += left[i];
      if (l_mid > l_mid_max) l_mid_max = l_mid;
    }

    vector<int> right(nums.begin() + nums.size() / 2, nums.end());
    int r = maxSubArray(right);

    int r_mid = right[0];
    int r_mid_max = r_mid;
    for (int i = 1; i < right.size(); ++i) {
      r_mid += right[i];
      if (r_mid > r_mid_max) r_mid_max = r_mid;
    }

    if (l >= r && l >= (l_mid_max + r_mid_max)) return l;
    if (r >= l && r >= (l_mid_max + r_mid_max)) return r;
    return l_mid_max + r_mid_max;
  }
};