LeetCode 0053. 最大子数组和:DP 或 递归(线段树入门题?)

news/2024/4/17 16:34:59

【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]) cnt=max(cnt+nums[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(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

方法二:递归(分治)

写一个函数 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的子数组的:

  1. lSum: 以 n u m s [ l ] nums[l] nums[l]为起点的最大子数组和
  2. rSum: 以 n u m s [ r ] nums[r] nums[r]为终点的最大子数组和
  3. MSum: 最大子数组和
  4. 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,2l+r⌋)(记为 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,2l+r+1,r)(记为 r S t a t u s rStatus rStatus)。递归终止条件为 l = r l=r l=r(只有单个元素)。

于是就有:

  1. 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) lSum=max(lStatus.lSum,lStatus.iSum+rStatus.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[⌊2l+r⌋]和跨过)
  2. 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) rSum=max(rStatus.rSum,lStatus.rSum+rStatus.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[⌊2l+r⌋]和跨过)
  3. 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) MSum=max(lStatus.MSum,rStatus.MSum,lStatus.rSum+rStatus.lSum)(左半部分最大子数组和、右半部分最大子数组和、跨过 n u m s [ ⌊ l + r 2 ⌋ ] nums[\lfloor\frac{l + r}{2}\rfloor] nums[⌊2l+r⌋]的子数组和)
  4. 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 iSum=lStatus.iSum+rStatus.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(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]
"""

方法二意义何在?

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

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

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

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

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


https://www.xjx100.cn/news/3090446.html

相关文章

以“防方视角”观Shiro反序列化漏洞

为方便您的阅读&#xff0c;可点击下方蓝色字体&#xff0c;进行跳转↓↓↓ 01 案例概述02 攻击路径03 防方思路 01 案例概述 这篇文章来自微信公众号“潇湘信安”&#xff0c;记录的某师傅如何发现、利用Shiro反序列化漏洞&#xff0c;又是怎样绕过火绒安全防护实现文件落地、…

开发仿抖音APP遇到的问题和解决方案

uni-app如何引入阿里矢量库图标/uniapp 中引入 iconfont 文件报错文件查找失败 uni-app如何引入阿里矢量库图标 - 知乎 uniapp 中引入 iconfont 文件报错文件查找失败&#xff1a;‘./iconfont.woff?t1673007495384‘ at App.vue:6_宝马金鞍901的博客-CSDN博客 将课件中的cs…

ubuntu linux C/C++环境搭建

目录 前言 1.1 vim安装与配置 ​编辑 1.2 vim配置 1.3 gcc g编译器的安装 与gdb调试器的安装 1.4 写个C/C程序测试一下 1.6 vscode安装 1.7 vscode插件下载​编辑 前言 在开始C之前&#xff0c;我们需要搭建好C的开发环境&#xff0c;我这里使用的操作系统是ubuntu Linux&a…

自然语言处理:Transformer与GPT

Transformer和GPT&#xff08;Generative Pre-trained Transformer&#xff09;是深度学习和自然语言处理&#xff08;NLP&#xff09;领域的两个重要概念&#xff0c;它们之间存在密切的关系但也有明显的不同。 1 基本概念 1.1 Transformer基本概念 Transformer是一种深度学…

流体的压力

压力是流体力学中很重要的物理量&#xff0c;国际标准单位为 Pa&#xff08;帕斯卡&#xff09;&#xff0c;其他常用单位包括 MPa&#xff08;兆帕&#xff09;、atm&#xff08;标准大气压&#xff09;、Torr&#xff08;托&#xff09; 等。 在流体内部&#xff0c;压力是标…

王者荣耀游戏

游戏运行如下&#xff1a; sxt Background package sxt;import java.awt.*; //背景类 public class Background extends GameObject{public Background(GameFrame gameFrame) {super(gameFrame);}Image bg Toolkit.getDefaultToolkit().getImage("C:\\Users\\24465\\D…

SVG圆形 <circle>的示例代码

本专栏是汇集了一些HTML常常被遗忘的知识&#xff0c;这里算是温故而知新&#xff0c;往往这些零碎的知识点&#xff0c;在你开发中能起到炸惊效果。我们每个人都没有过目不忘&#xff0c;过久不忘的本事&#xff0c;就让这一点点知识慢慢渗透你的脑海。 本专栏的风格是力求简洁…

MATLAB中std函数用法

目录 语法 说明 示例 矩阵列的标准差 三维数组的标准差 指定标准差权重 矩阵行的标准差 数组页的标准差 排除缺失值的标准差 标准差和均值 标准差 std函数的功能是得到标准差。 语法 S std(A) S std(A,w) S std(A,w,"all") S std(A,w,dim) S std(A…