0001-0100 - 0053-最大子序和 - 《LeetCode》

题目链接
题目描述
示例
- 示例1：
提示
进阶
思路
题解
复杂度分析

题目链接

点击查看【music163】

题目描述

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

示例

示例1：

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

提示

1 <= nums.length <= 3 * 10
-10 <= nums[i] <= 10

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

思路

思路1：动态规划
我们使用dp[i]表示以第i个数结尾的连续子数组的最大和，那么原问题等价为求：
其中，
我们可以将dp[]优化成单个变量dp

思路2：贪心
设sum为连续数组的和，设当前的元素为nums[i]，要使得和最大，我们就要保证之前的累加和sum不小于0；换言之，如果之前的累加和小于0，那么只会让当前的数字变小，此时需要重新开始寻找子串。

思路3：分治法（线段树）
此方法为进阶方法，基于线段树的分治法。此方法可以求任意区间的连续子数组的最大和。
一般地，对于区间[l,r]，我们维护四个变量：
lSum表示[l,r]内以l为左端点的最大子段和
rSum表示[l,r]内以r为右端点的最大子段和
mSum表示[l,r]内的最大子段和
iSum表示[l,r]的区间和

下面采用分治的思想，首先递归终点为l==r，此时上述四个量都为nums[l]。设[l,m]左子区间，[m+1,r]为右子区间。对于一般的情况：

[l,r]的 iSum 等于左右子区间 iSum之和。
[l,r]的 lSum 有两种情况，一是等于左子区间的lSum，二是等于左子区间的iSum加上右子区间的lSum，二者取最大。
[l,r]的 rSum 同理。

[l,r]的 mSum 有三种情况，分别为不跨越m和跨越m；不跨越m为左右子区间 mSum 的最大值，若跨越m，求左右子区间的 mSum 和；三者取最大。

题解

思路1：动态规划

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

思路2：贪心

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

思路3：分治法（线段树）

class Solution {
 private:
  struct S {
      int lSum, rSum, mSum, iSum;
  };

  S lookBack(S l, S r) {
      int iSum = l.iSum + r.iSum;
      int lSum = max(l.lSum, l.iSum + r.lSum);
      int rSum = max(r.rSum, l.rSum + r.iSum);
      int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);

      return S{lSum, rSum, mSum, iSum};
  }

  S build(vector<int>& nums, int l, int r) {
      if (l == r) {
          return S{nums[l], nums[l], nums[l], nums[l]};
      }
      int m = ((r - l) >> 1) + l;
      S lSub = build(nums, l, m);
      S rSub = build(nums, m + 1, r);
      return lookBack(lSub, rSub);
  }

 public:
  int maxSubArray(vector<int>& nums) {
      return build(nums, 0, nums.size() - 1).mSum;
  }
};