53. 最大子数组和 : 图解从 O(n) 的常规理解到 O(n) 的分治做法

题目描述

这是 LeetCode 上的 「53. 最大子数组和」 ,难度为 「中等」

Tag : 「前缀和」、「区间求和问题」、「线性 DP」、「分治」

给你一个整数数组 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

提示:

进阶:如果你已经实现复杂度为 的解法,尝试使用更为精妙的分治法求解。

前缀和 or 线性 DP

当要我们求「连续段」区域和的时候,要很自然的想到「前缀和」。

所谓前缀和,是指对原数组“累计和”的描述,通常是指一个与原数组等长的数组。

设前缀和数组为 sum,**sum 的每一位记录的是从「起始位置」到「当前位置」的元素和**。例如 是指原数组中“起始位置”到“位置 x”这一连续段的元素和。

有了前缀和数组 sum,当我们求连续段 的区域和时,利用「容斥原理」,便可进行快速求解。

通用公式:ans = sum[j] - sum[i - 1]

image.png
image.png

由于涉及 -1 操作,为减少边界处理,我们可让前缀和数组下标从 开始。在进行快速求和时,再根据原数组下标是否从 开始,决定是否进行相应的下标偏移。

学习完一维前缀和后,回到本题。

先用 nums 预处理出前缀和数组 sum,然后在遍历子数组右端点 j 的过程中,通过变量 m 动态记录已访问的左端点 i 的前缀和最小值。最终,在所有 sum[j] - m 的取值中选取最大值作为答案。

代码实现上,我们无需明确计算前缀和数组 sum,而是使用变量 s 表示当前累计的前缀和(充当右端点),并利用变量 m 记录已访问的前缀和的最小值(充当左端点)即可。

「本题除了将其看作为「前缀和裸题用有限变量进行空间优化」以外,还能以「线性 DP」角度进行理解。」

定义 为考虑前 个元素,且第 必选的情况下,形成子数组的最大和。

不难发现,仅考虑前 个元素,且 必然参与的子数组中。要么是 自己一个成为子数组,要么与前面的元素共同组成子数组。

因此,状态转移方程:

由于 仅依赖于 进行转移,可使用有限变量进行优化,因此写出来的代码也是和上述前缀和角度分析的类似。

Java 代码:

class Solution {
    public int maxSubArray(int[] nums) {
        int s = 0, m = 0, ans = -10010;
        for (int x : nums) {
            s += x;
            ans = Math.max(ans, s - m);
            m = Math.min(m, s);
        }
        return ans;
    }
}

C++ 代码:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int s = 0, m = 0, ans = -10010;
        for (int x : nums) {
            s += x;
            ans = max(ans, s - m);
            m = min(m, s);
        }
        return ans;
    }
};

Python 代码:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        s, m, ans = 00-10010
        for x in nums:
            s += x
            ans = max(ans, s - m)
            m = min(m, s)
        return ans

TypeScript 代码:

function maxSubArray(nums: number[]): number {
    let s = 0, m = 0, ans = -10010;
    for (let x of nums) {
        s += x;
        ans = Math.max(ans, s - m);
        m = Math.min(m, s);
    }
    return ans;
};
  • 时间复杂度:
  • 空间复杂度:

分治

“分治法”的核心思路是将大问题拆分成更小且相似的子问题,通过递归解决这些子问题,最终合并子问题的解来得到原问题的解。

实现分治,关键在于对“递归函数”的设计(入参 & 返回值)。

在涉及数组的分治题中,左右下标 lr 必然会作为函数入参,因为它能用于表示当前所处理的区间,即小问题的范围。

对于本题,仅将最大子数组和(答案)作为返回值并不足够,因为单纯从小区间的解无法直接推导出大区间的解,我们需要一些额外信息来辅助求解。

具体的,我们可以将返回值设计成四元组,分别代表 区间和前缀最大值后缀最大值最大子数组和,用 [sum, lm, rm, max] 表示。

有了完整的函数签名 int[] dfs(int[] nums, int l, int r),考虑如何实现分治:

  1. 根据当前区间 的长度进行分情况讨论:
    1. ,只有一个元素,区间和为 ,而 最大子数组和、前缀最大值 和 后缀最大值 由于允许“空数组”,因此均为
    2. 否则,将当前问题划分为两个子问题,通常会划分为两个相同大小的子问题,划分为 两份,递归求解,其中

随后考虑如何用“子问题”的解合并成“原问题”的解:

  1. 「合并区间和 (sum):」 当前问题的区间和等于左右两个子问题的区间和之和,即 sum = left[0] + right[0]
  2. 「合并前缀最大值 (lm):」 当前问题的前缀最大值可以是左子问题的前缀最大值,或者左子问题的区间和加上右子问题的前缀最大值。即 lm = max(left[1], left[0] + right[1])
  3. 「合并后缀最大值 (rm):」 当前问题的后缀最大值可以是右子问题的后缀最大值,或者右子问题的区间和加上左子问题的后缀最大值。即 rm = max(right[2], right[0] + left[2])
  4. 「合并最大子数组和 (max):」 当前问题的最大子数组和可能出现在左子问题、右子问题,或者跨越左右两个子问题的边界。因此, max 可以通过 max(left[3], right[3], left[2] + right[1]) 来得到。

一些细节:由于我们在计算 lmrmmax 的时候允许数组为空,而答案对子数组的要求是至少包含一个元素。因此对于 nums 全为负数的情况,我们会错误得出最大子数组和为 0 的答案。针对该情况,需特殊处理,遍历一遍 nums,若最大值为负数,直接返回最大值。

Java 代码:

class Solution {
    // 返回值: [sum, max, lm, rm] = [区间和, 最大子数组和, 前缀最大值, 后缀最大值]
    int[] dfs(int[] nums, int l, int r) {
        if (l == r) {
            int t = Math.max(nums[l], 0);
            return new int[]{nums[l], t, t, t};
        }
        // 划分成两个子区间,分别求解
        int mid = l + r >> 1;
        int[] left = dfs(nums, l, mid), right = dfs(nums, mid + 1, r);
        // 组合左右子区间的信息,得到当前区间的信息
        int[] ans = new int[4];
        ans[0] = left[0] + right[0]; // 当前区间和
        ans[1] = Math.max(left[1], left[0] + right[1]); // 当前区间前缀最大值
        ans[2] = Math.max(right[2], right[0] + left[2]); // 当前区间后缀最大值
        ans[3] = Math.max(Math.max(left[3], right[3]), left[2] + right[1]); // 最大子数组和
        return ans;
    }
    public int maxSubArray(int[] nums) {
        int m = nums[0];
        for (int x : nums) m = Math.max(m, x);
        if (m <= 0return m;
        return dfs(nums, 0, nums.length - 1)[3];
    }
}

C++ 代码:

class Solution {
public:
    // 返回值: [sum, max, lm, rm] = [区间和, 最大子数组和, 前缀最大值, 后缀最大值]
    vector<intdfs(vector<int>& nums, int l, int r) {
        if (l == r) {
            int t = max(nums[l], 0);
            return {nums[l], t, t, t};
        }
        // 划分成两个子区间,分别求解
        int mid = l + r >> 1;
        auto left = dfs(nums, l, mid), right = dfs(nums, mid + 1, r);
        // 组合左右子区间的信息,得到当前区间的信息
        vector<intans(4);
        ans[0] = left[0] + right[0]; // 当前区间和
        ans[1] = max(left[1], left[0] + right[1]); // 当前区间前缀最大值
        ans[2] = max(right[2], right[0] + left[2]); // 当前区间后缀最大值
        ans[3] = max({left[3], right[3], left[2] + right[1]}); // 最大子数组和
        return ans;
    }
    int maxSubArray(vector<int>& nums) {
        int m = nums[0];
        for (int x : nums) m = max(m, x);
        if (m <= 0return m;
        return dfs(nums, 0, nums.size() - 1)[3];
    }
};

Python 代码:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def dfs(l, r):
            if l == r:
                t = max(nums[l], 0)
                return [nums[l], t, t, t]
            # 划分成两个子区间,分别求解
            mid = (l + r) // 2
            left, right = dfs(l, mid), dfs(mid + 1, r)
            # 组合左右子区间的信息,得到当前区间的信息
            ans = [0] * 4
            ans[0] = left[0] + right[0# 当前区间和
            ans[1] = max(left[1], left[0] + right[1]) # 当前区间前缀最大值
            ans[2] = max(right[2], right[0] + left[2]) # 当前区间后缀最大值
            ans[3] = max(left[3], right[3], left[2] + right[1]) # 最大子数组和
            return ans
        
        m = max(nums)
        if m <= 0:
            return m
        return dfs(0, len(nums) - 1)[3]

TypeScript 代码:

function maxSubArray(nums: number[]): number {
    const dfs = function (l: number, r: number): number[] {
        if (l == r) {
            const t = Math.max(nums[l], 0);
            return [nums[l], t, t, t];
        }
        // 划分成两个子区间,分别求解
        const mid = (l + r) >> 1;
        const left = dfs(l, mid), right = dfs(mid + 1, r);
        // 组合左右子区间的信息,得到当前区间的信息
        const ans = Array(4).fill(0);
        ans[0] = left[0] + right[0]; // 当前区间和
        ans[1] = Math.max(left[1], left[0] + right[1]); // 当前区间前缀最大值
        ans[2] = Math.max(right[2], right[0] + left[2]); // 当前区间后缀最大值
        ans[3] = Math.max(left[3], right[3], left[2] + right[1]); // 最大子数组和
        return ans;
    }
    
    const m = Math.max(...nums);
    if (m <= 0return m;
    return dfs(0, nums.length - 1)[3];
};
  • 时间复杂度:
  • 空间复杂度:

最后

这是我们「刷穿 LeetCode」系列文章的第 No.53 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/167697.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

刚果(布)市场开发攻略,收藏一篇就够了

刚果&#xff08;布&#xff09;是非洲西部的一个国家&#xff0c;中国是刚果布第一大出口国&#xff0c;第二个进口国&#xff0c;经济联系比较紧密&#xff0c;从中国进口产品主要机械配件、建材、电机、针织或钩编的服装及衣着附件、蔬菜、水果等。本身国内治安良好&#xf…

抖音直播招聘报白又叫报抖音的白名单要不然就会封禁直播间

抖音直播招聘报白&#xff0c;又叫报抖音的白名单&#xff0c;只有进了抖音白名单里才能在直播间说招聘或者找工作等相关词&#xff0c;要不然就会封禁直播间&#xff0c;小视频也不会给推流&#xff0c;还会限流&#xff0c;但是如果做了抖音报白&#xff0c;官方也会给一部分…

学习教授LLM逻辑推理11.19

学习教授LLM逻辑推理 摘要1 引言2前言2.1事件关系提取2.2 演绎推理 3 揭示逻辑推理中的LLMS3.1 LLM如何执行任务3.1.1数据源3.1.2实验装置3.1.3 分析 3.2 LLM如何执行抽象多跳推理&#xff1f;3.2.1数据来源3.2.2 实验装置。3.2.3 分析。 4 逻辑推理教学4.1 LLM的上下文学习4.2…

学生作业管理系统的设计与实现-计算机毕业设计源码20912

摘 要 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&#xff0c;通过科技手段提高自身的优势&#xff1b;对于学生作业管理系统当然也不能排除在外&#xff0c;随着网络技术的不断成熟&#xff0c;带动了学生作业管理系统&#xff0c;它彻底改变了过…

vue如何开启gzip压缩

什么是gzip&#xff1a; Gzip 是一种压缩算法&#xff0c;在网络传输中使用非常普遍。 需要注意的是&#xff0c;Gzip 压缩仅对于文本类型的资源有明显提示&#xff0c;压缩后的体积大约是压缩前的 1/3。 但是对于图片&#xff0c;音视频等媒体资源&#xff0c;本身就采用了…

lvm操作和扩容根分区

扩展逻辑卷 [rootlocalhost ~]# pvcreate /dev/sdb1 vgextend vg1 /dev/sdb1&#xff08;表示将/dev/sdb1扩展到centos卷组&#xff0c;扩展卷组就是将其它分好的区加入卷组&#xff09; [rootlocalhost ~]# vgextend centos /dev/sdb1[rootlocalhost ~]# lvextend -L 50G /…

【图像分类】【深度学习】【轻量级网络】【Pytorch版本】MobileNets_V2模型算法详解

【图像分类】【深度学习】【轻量级网络】【Pytorch版本】MobileNets_V2模型算法详解 文章目录 【图像分类】【深度学习】【轻量级网络】【Pytorch版本】MobileNets_V2模型算法详解前言MobleNet_V2讲解反向残差结构(Inverted Residuals)兴趣流形(Manifold of interest)线性瓶颈层…

德思特分享丨一文带你了解ADC测试参数有哪些?

来源&#xff1a;德思特测量测试 德思特分享丨一文带你了解ADC测试参数有哪些&#xff1f; 一文带你了解ADC测试参数有哪些 模数转换器&#xff08;ADC&#xff09;是数字电子系统中重要组成部分&#xff0c;用于捕获外部世界的模拟信号&#xff0c;如声音、图像、温度、压力…

修改bat文件默认编辑软件

Windows默认编辑bat文件的软件是自带的文本编辑器。无法高亮显示bat中的命令。 修改方式一&#xff1a; 打开注册表文件&#xff0c;变更键值 HKEY_CLASSES_ROOT\batfile\shell\edit\command 对应软件地址 修改方式二&#xff1a; 制作批处理文件&#xff0c;代码如下&#x…

【Highway-env】IntersectionEnv代码阅读

文章目录 主要完成任务代码结构1.action space2.default_config3.reward_agent_rewards_agent_reward_reward_rewards小结 4.terminated & truncated5.reset_make_road_make_vehicles_spawn_vehicle 6.step 主要完成任务 IntersectionEnv继承自AbstractEnv,主要完成以下4个…

Oracle数据库透明加密 安当加密

安当TDE透明加密组件是一种用于数据保护的解决方案&#xff0c;它对数据进行加密&#xff0c;以防止未经授权的访问和数据泄露。 以下是安当TDE透明加密组件的主要功能介绍&#xff1a; 数据保护&#xff1a;安当TDE透明加密组件可以对数据库中的敏感数据进行加密&#xff0c;…

基于springboot实现大学生就业服务平台系统项目【项目源码】

基于springboot实现大学生就业服务平台系统演示 Java技术 Java是由SUN公司推出&#xff0c;该公司于2010年被oracle公司收购。Java本是印度尼西亚的一个叫做爪洼岛的英文名称&#xff0c;也因此得来java是一杯正冒着热气咖啡的标识。Java语言在移动互联网的大背景下具备了显著…

深度学习人脸表情识别算法 - opencv python 机器视觉 计算机竞赛

文章目录 0 前言1 技术介绍1.1 技术概括1.2 目前表情识别实现技术 2 实现效果3 深度学习表情识别实现过程3.1 网络架构3.2 数据3.3 实现流程3.4 部分实现代码 4 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 深度学习人脸表情识别系…

如何构建更简洁的前端架构?

目录 为什么需要前端架构&#xff1f; 那么&#xff0c;前端架构是什么样的呢&#xff1f; 使用了哪些层&#xff1f; 那么&#xff0c;这种架构会出什么问题呢&#xff1f; 我们应该如何避免这些错误&#xff1f; 哪些原则应适用于组件&#xff1f; Anti-Patterns 反模…

HCIA-实验命令基础学习:

视频学习&#xff1a; 第一部分&#xff1a;基础学习。 19——子网掩码。 27——防火墙配置&#xff1a; 32——企业级路由器配置&#xff1a; 基础实验完成&#xff1a;&#xff08;完成以下目录对应的实验&#xff0c;第一部分基础实验就完成。&#xff09; 方法&#xff…

儿童家居服 I 童年很短,请尽情打扮吧

厚实细腻的双面北极绒面料 软糯亲肤&#xff0c;上身效果极佳 经典宽松版型&#xff0c;对身材的包容性很强 帽子上的小熊刺绣精致又可爱 袖口处还有小熊掌的刺绣哦 满满的少女心&#xff0c;也太适合女宝宝了 松紧裤腰和束脚设计&#xff0c;防风保暖做到实处 这么好看…

【数据结构&C++】超详细一文带小白轻松全面理解 [ 二叉平衡搜索树-AVL树 ]—— [从零实现&逐过程分析&代码演示简练易懂]

前言 大家好吖&#xff0c;欢迎来到 YY 滴C系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过C的老铁 主要内容含&#xff1a; 欢迎订阅 YY滴C专栏&#xff01;更多干货持续更新&#xff01;以下是传送门&#xff01; 目录 一.AVL树的概念二.AVL树节点的定义(代码…

Python开源自动化工具Playwright安装及介绍

一个非常强大的自动化项目叫 playwright-python 它支持主流的浏览器&#xff0c;包含&#xff1a;Chrome、Firefox、Safari、Microsoft Edge 等&#xff0c;同时支持以无头模式、有头模式运行&#xff0c;并提供了同步、异步的 API&#xff0c;可以结合 Pytest 测试框架 使用&…

IPO解读丨高处不胜寒,澜沧古茶低头取暖?

自A股注册制改革不断深化并全面落地后&#xff0c;不少意欲登陆资本市场的企业转战港股。这个过程中&#xff0c;诞生了很多以“港股”为前缀的“第一股”——“白酒第一股”珍酒李渡、“水果零售第一股”百果园、“智能驾驶第一股”知行汽车、“运动科技第一股”Keep…… 由A…

STM32与ADXL345加速度计的无线传输与监测应用

ADXL345是一款三轴数字输出加速度计&#xff0c;能够测量出物体在三个方向上的加速度。本文将介绍如何将ADXL345加速度计与STM32微控制器结合使用&#xff0c;通过无线通信技术实现加速度数据的传输与监测。 一、ADXL345与STM32概述 1. ADXL345加速度计 ADXL345是一款低功耗…