leetcode 链接：最大子序和

题目

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

示例：

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

输入：nums = [1]
输出：1

输入：nums = [0]
输出：0

输入：nums = [-1]
输出：-1

输入：nums = [-100000]
输出：-100000

解答 & 代码

解法一：动态规划

类似题目：[容易] 121. 买卖股票的最佳时机

时间复杂度 O(N)，空间复杂度 O(1)

遍历一次数组，即可依次求出以每个下标 i 为结尾的最大子序和 preSum[i] = preSum[i-1] > 0 ? preSum[i-1] + nums[i] : nums[i] （动态规划转移方程）

• 因为 preSum[i] 只和 preSum[i-1] 有关，因此可以优化为 preSum = preSum > 0 ? preSum + nums[i] : nums[i] ，使得空间复杂度为 O(1)

在遍历数组的同时，将以下标 i 为结尾的最大子序和 preSum 和最大子序和 maxSum 比较来更新 maxSum

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int preSum = 0;
        int maxSum = nums[0];   // 注意初始赋值 nums[0] 而不是 0，否则对于 nums=[-1] 的情况就错误地返回结果 0 了
        for(int i = 0; i < nums.size(); ++i)
        {
            preSum = preSum > 0 ? preSum + nums[i] : nums[i];
            maxSum = preSum > maxSum ? preSum : maxSum;
        }
        return maxSum;
    }
};

执行结果：

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 68.07% 的用户
内存消耗：12.7 MB, 在所有 C++ 提交中击败了 81.58% 的用户

解法二：分治法

设序列长度为 N，就递归过程看作二叉树的后序遍历（先递归左、右子树，再合并信息）

• 时间复杂度 O(N)：相当于遍历二叉树的所有节点

• 空间复杂度 O(logN)：递归用到的栈空间（树的深度）

  struct ReturnType {    // 要维护的区间信息
    int maxSum;        // 区间内的最大子序和
    int leftSum;    // 以区间左端点为起点的最大子序和
    int rightSum;    // 以区间右端点为终点的最大子序和
    int totalSum;    // 区间元素总和
    ReturnType(int mSum, int lSum, int rSum, int tSum): maxSum(mSum), leftSum(lSum), rightSum(rSum), totalSum(tSum) {}
  };
  class Solution {
  private:
    // 分治（递归）计算最大子序和
    ReturnType calMaxSubArray(vector<int> nums, int left, int right) {
        // 递归结束条件
        if(left == right)
            return ReturnType{nums[left], nums[left], nums[left], nums[left]};
  
        // 将区间划分为左、右两个子区间
        int mid = (left + right) / 2;    // 区间中点下标
        // 分别递归得到左、右子区间的信息
        ReturnType leftData = calMaxSubArray(nums, left, mid);
        ReturnType rightData = calMaxSubArray(nums, mid + 1, right);
  
        // 合并区间信息
        int leftSum = (leftData.totalSum + rightData.leftSum > leftData.leftSum) ? leftData.totalSum + rightData.leftSum : leftData.leftSum;
        int rightSum = (rightData.totalSum + leftData.rightSum > rightData.rightSum) ? rightData.totalSum + leftData.rightSum : rightData.rightSum;
        int totalSum = leftData.totalSum + rightData.totalSum;
        int maxSum = (leftData.maxSum > rightData.maxSum) ? leftData.maxSum : rightData.maxSum;
        maxSum = (leftData.rightSum + rightData.leftSum > maxSum) ? leftData.rightSum + rightData.leftSum : maxSum;
        return ReturnType{maxSum, leftSum, rightSum, totalSum};
    }
  public:
    int maxSubArray(vector<int>& nums) {
        return calMaxSubArray(nums, 0, nums.size() - 1).maxSum;
    }
  };
  

  执行结果： ``` 执行结果：通过

执行用时：576 ms, 在所有 C++ 提交中击败了 6.35% 的用户 内存消耗：674.4 MB, 在所有 C++ 提交中击败了 5.30% 的用户 ```