网站开发前端规范,h5游戏平台代理,wordpress导入插件下载,网络经营范围包括哪些【LetMeFly】53.最大子数组和#xff1a;DP 或 递归
力扣题目链接#xff1a;https://leetcode.cn/problems/maximum-subarray/
给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最…【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
使用动态规划的话思路比较简单使用一个变量 c n t cnt cnt记录以当前元素为结尾的最大子数组和。
这样我们只需要遍历一遍 n u m s nums nums数组使用公式 c n t max ( c n t n u m s [ i ] , n u m s [ i ] ) cnt \max(cnt nums[i], nums[i]) cntmax(cntnums[i],nums[i])维护 c n t cnt cnt并记得更新答案的最大值即可。
时间复杂度 O ( l e n ( n u m s ) ) O(len(nums)) O(len(nums))空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C
class Solution {
public:int maxSubArray(vectorint 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方法二递归分治
写一个函数 g e t ( n u m s , l , r ) get(nums, l, r) get(nums,l,r)返回 n u m s nums nums数组从 l l l到 r r r的子数组的
lSum: 以 n u m s [ l ] nums[l] nums[l]为起点的最大子数组和rSum: 以 n u m s [ r ] nums[r] nums[r]为终点的最大子数组和MSum: 最大子数组和iSum: 和
那么我们就可以愉快地进行递归啦
对于 g e t ( n u m s , l , r ) get(nums, l, r) get(nums,l,r)我们可以分别求出 g e t ( n u m s , l , ⌊ l r 2 ⌋ ) get(nums, l, \lfloor\frac{l r}{2}\rfloor) get(nums,l,⌊2lr⌋)记为 l S t a t u s lStatus lStatus和 g e t ( n u m s , ⌊ l r 2 ⌋ 1 , r ) get(nums, \lfloor\frac{l r}{2}\rfloor 1, r) get(nums,⌊2lr⌋1,r)记为 r S t a t u s rStatus rStatus。递归终止条件为 l r lr lr只有单个元素。
于是就有 l S u m max ( l S t a t u s . l S u m , l S t a t u s . i S u m r S t a t u s . l S u m ) lSum \max(lStatus.lSum, lStatus.iSum rStatus.lSum) lSummax(lStatus.lSum,lStatus.iSumrStatus.lSum)以 n u m s [ l ] nums[l] nums[l]为起点不跨过 n u m s [ ⌊ l r 2 ⌋ ] nums[\lfloor\frac{l r}{2}\rfloor] nums[⌊2lr⌋]和跨过 r S u m max ( r S t a t u s . r S u m , l S t a t u s . r S u m r S t a t u s . i S u m ) rSum \max(rStatus.rSum, lStatus.rSum rStatus.iSum) rSummax(rStatus.rSum,lStatus.rSumrStatus.iSum)以 n u m s [ r ] nums[r] nums[r]为终点不跨过 n u m s [ ⌊ l r 2 ⌋ ] nums[\lfloor\frac{l r}{2}\rfloor] nums[⌊2lr⌋]和跨过 M S u m max ( l S t a t u s . M S u m , r S t a t u s . M S u m , l S t a t u s . r S u m r S t a t u s . l S u m ) MSum \max(lStatus.MSum, rStatus.MSum, lStatus.rSum rStatus.lSum) MSummax(lStatus.MSum,rStatus.MSum,lStatus.rSumrStatus.lSum)左半部分最大子数组和、右半部分最大子数组和、跨过 n u m s [ ⌊ l r 2 ⌋ ] nums[\lfloor\frac{l r}{2}\rfloor] nums[⌊2lr⌋]的子数组和 i S u m l S t a t u s . i S u m r S t a t u s . i S u m iSum lStatus.iSum rStatus.iSum iSumlStatus.iSumrStatus.iSum左半右半数组和 之和
最终返回 g e t ( n u m s , 0 , l e n ( n u m s ) − 1 ) . M S u m get(nums, 0, len(nums) - 1).MSum get(nums,0,len(nums)−1).MSum即可。
时间复杂度 O ( l e n ( n u m s ) ) O(len(nums)) O(len(nums))相当于后序遍历了一遍二叉树空间复杂度 O ( log l e n ( n u m s ) ) O(\log len(nums)) O(loglen(nums))空间复杂度主要来源于递归
AC代码
C
struct Status {int lSum, rSum, MSum, iSum;
};class Solution {
private:Status get(vectorint 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(vectorint 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] 99a
[1, 2, 3]b
[99]方法二意义何在
相较于方法一方法二的时间复杂度没有提升空间复杂度反而更高了。那么方法二的意义何在
这道题只问了“整个数组的”最大子数组和。但是如果某天遇到了一道题问你 1 0 5 10^5 105次且每次随机问一个 [ l , r ] [l, r] [l,r]的最大子数组和 呢
那么我们使用方法二并且将每层的结果记录下来就能做到每次查询都在 O ( log n ) O(\log n) O(logn)的时间复杂度下返回结果。
这就是没有懒标记的线段树。 同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/134504375
