LeetCode 0053. 最大子数组和：DP 或 递归（线段树入门题？）

【LetMeFly】53.最大子数组和：DP 或 递归

力扣题目链接：https://leetcode.cn/problems/maximum-subarray/

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

子数组 是数组中的一个连续部分。

 

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

 

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

 

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

方法一：DP

使用动态规划的话思路比较简单，使用一个变量$cnt$记录以当前元素为结尾的最大子数组和。

这样，我们只需要遍历一遍$nums$数组，使用公式$cnt=\max (cnt+nums[i],nums[i])$维护$cnt$，并记得更新答案的最大值即可。

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(1)$

AC代码

C++

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

Python

# from typing import Listclass Solution:def maxSubArray(self, nums: List[int]) -> int:ans, cnt = nums[0], nums[0]for i in range(1, len(nums)):cnt = max(cnt + nums[i], nums[i])ans = max(ans, cnt)return ans

方法二：递归（分治）

写一个函数$get(nums,l,r)$，返回$nums$数组从$l$到$r$的子数组的：

1. lSum: 以$nums[l]$为起点的最大子数组和
2. rSum: 以$nums[r]$为终点的最大子数组和
3. MSum: 最大子数组和
4. iSum: 和

那么，我们就可以愉快地进行递归啦！

对于$get(nums,l,r)$，我们可以分别求出$get(nums,l,\lfloor \frac{l+r}{2}\rfloor )$（记为$lStatus$）和$get(nums,\lfloor \frac{l+r}{2}\rfloor +1,r)$（记为$rStatus$）。递归终止条件为$l=r$（只有单个元素）。

于是就有：

1. $lSum=\max (lStatus.lSum,lStatus.iSum+rStatus.lSum)$（以$nums[l]$为起点，不跨过$nums[\lfloor \frac{l+r}{2}\rfloor ]$和跨过）
2. $rSum=\max (rStatus.rSum,lStatus.rSum+rStatus.iSum)$（以$nums[r]$为终点，不跨过$nums[\lfloor \frac{l+r}{2}\rfloor ]$和跨过）
3. $MSum=\max (lStatus.MSum,rStatus.MSum,lStatus.rSum+rStatus.lSum)$（左半部分最大子数组和、右半部分最大子数组和、跨过$nums[\lfloor \frac{l+r}{2}\rfloor ]$的子数组和）
4. $iSum=lStatus.iSum+rStatus.iSum$（左半右半数组和 之和）

最终返回$get(nums,0,len(nums)-1).MSum$即可。

• 时间复杂度$O(len(nums))$（相当于后序遍历了一遍二叉树）
• 空间复杂度$O(\log len(nums))$（空间复杂度主要来源于递归）

AC代码

C++

struct Status {int lSum, rSum, MSum, iSum;
};class Solution {
private:Status get(vector<int>& a, int l, int r) {  // get[l, r]if (l == r) {return {a[l], a[l], a[l], a[l]};}int m = (l + r) >> 1;Status lStatus = get(a, l, m);Status rStatus = get(a, m + 1, r);return {max(lStatus.lSum, lStatus.iSum + rStatus.lSum),max(rStatus.rSum, lStatus.rSum + rStatus.iSum),max(lStatus.MSum, max(rStatus.MSum, lStatus.rSum + rStatus.lSum)),lStatus.iSum + rStatus.iSum};}
public:int maxSubArray(vector<int>& nums) {return get(nums, 0, nums.size() - 1).MSum;}
};

Python

# from typing import Listclass Status:def __init__(self, lSum: int, rSum: int, MSum: int, iSum: int) -> None:self.lSum = lSumself.rSum = rSumself.MSum = MSumself.iSum = iSumclass Solution:def get(self, nums: List[int], l: int, r: int) -> Status:if l == r:return Status(nums[l], nums[l], nums[l], nums[l])m = (l + r) >> 1lStatus = self.get(nums, l, m)rStatus = self.get(nums, m + 1, r)return Status(max(lStatus.lSum, lStatus.iSum + rStatus.lSum),max(rStatus.rSum, lStatus.rSum + rStatus.iSum),max(lStatus.MSum, rStatus.MSum, lStatus.rSum + rStatus.lSum),lStatus.iSum + rStatus.iSum)def maxSubArray(self, nums: List[int]) -> int:return self.get(nums, 0, len(nums) - 1).MSum"""为何不用切片作为参数？
>>> a = [1, 2, 3]
>>> a
[1, 2, 3]
>>> b = a[1:2]
>>> b
[2]
>>> b[0] = 99
>>> a
[1, 2, 3]
>>> b
[99]
"""

方法二意义何在？

相较于方法一，方法二的时间复杂度没有提升，空间复杂度反而更高了。那么方法二的意义何在？

这道题只问了“整个数组的”最大子数组和。但是如果某天遇到了一道题，问你$10^5$次且每次随机问一个$[l,r]$的最大子数组和 呢？

那么我们使用方法二，并且将每层的结果记录下来，就能做到每次查询都在$O(\log n)$的时间复杂度下返回结果。

这就是没有懒标记的线段树。

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/134504375