首页 > 编程语言 >100道面试必会算法-09-最大子数组和(初探动态规划)

100道面试必会算法-09-最大子数组和(初探动态规划)

时间:2024-03-23 19:33:18浏览次数:28  
标签:最大 nums 09 问题 连续 数组 初探 100 dp

100道面试必会算法-09-最大子数组和(初探动态规划)

题目

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

解题思路

传送门:https://leetcode.cn/problems/maximum-subarray/solutions/9058/dong-tai-gui-hua-fen-zhi-fa-python-dai-ma-java-dai/

关键 1:理解题意

题目要我们找出和最大的连续子数组的值是多少,「连续」是关键字,连续很重要,不是子序列。

题目只要求返回结果,不要求得到最大的连续子数组是哪一个。这样的问题通常可以使用「动态规划」解决。

关键 2:如何定义子问题(如何定义状态)

设计状态思路:把不确定的因素确定下来,进而把子问题定义清楚,把子问题定义得简单。动态规划的思想通过解决了一个一个简单的问题,进而把简单的问题的解组成了复杂的问题的解。

我们不知道和最大的连续子数组一定会选哪一个数,那么我们可以求出所有经过输入数组的某一个数的连续子数组的最大和。

例如,示例 1 输入数组是 [-2,1,-3,4,-1,2,1,-5,4] ,我们可以求出以下子问题:

  • 子问题 1:经过 -2 的连续子数组的最大和是多少;
  • 子问题 2:经过 1 的连续子数组的最大和是多少;
  • 子问题 3:经过 -3 的连续子数组的最大和是多少;
  • 子问题 4:经过 4 的连续子数组的最大和是多少;
  • 子问题 5:经过 -1 的连续子数组的最大和是多少;
  • 子问题 6:经过 2 的连续子数组的最大和是多少;
  • 子问题 7:经过 1 的连续子数组的最大和是多少;
  • 子问题 8:经过 -5 的连续子数组的最大和是多少;
  • 子问题 9:经过 4 的连续子数组的最大和是多少。

一共 9 个子问题,这些子问题之间的联系并没有那么好看出来,这是因为子问题的描述还有不确定的地方(这件事情叫做「有后效性」,我们在本文的最后会讲解什么是「无后效性」)。

例如「子问题 3」:经过 -3 的连续子数组的最大和是多少。

「经过 -3 的连续子数组」我们任意举出几个:

  • [-2,1,-3,4]-3 是这个连续子数组的第 3 个元素;
  • [1,-3,4,-1]-3 是这个连续子数组的第 2 个元素; ……

我们不确定的是:-3 是连续子数组的第几个元素。那么我们就把 -3 定义成连续子数组的最后一个元素。在新的定义下,我们列出子问题如下:

  • 子问题 1:以 -2 结尾的连续子数组的最大和是多少;
  • 子问题 2:以 1 结尾的连续子数组的最大和是多少;
  • 子问题 3:以 -3 结尾的连续子数组的最大和是多少;
  • 子问题 4:以 4 结尾的连续子数组的最大和是多少;
  • 子问题 5:以 -1 结尾的连续子数组的最大和是多少;
  • 子问题 6:以 2 结尾的连续子数组的最大和是多少;
  • 子问题 7:以 1 结尾的连续子数组的最大和是多少;
  • 子问题 8:以 -5 结尾的连续子数组的最大和是多少;
  • 子问题 9:以 4 结尾的连续子数组的最大和是多少。

我们加上了「结尾的」,这些子问题之间就有了联系。我们单独看子问题 1 和子问题 2:

  • 子问题 1:以 -2结尾的连续子数组的最大和是多少;
    • -2 结尾的连续子数组是 [-2],因此最大和就是 -2
  • 子问题 2:以 1结尾的连续子数组的最大和是多少;
    • 1 结尾的连续子数组有 [-2,1][1] ,其中 [-2,1] 就是在「子问题 1」的后面加上 1 得到。-2+1=-1<1,因此「子问题 2」的答案是 1

大家发现了吗,如果编号为 i 的子问题的结果是负数或者 0 ,那么编号为 i + 1 的子问题就可以把编号为 i 的子问题的结果舍弃掉(这里 i 为整数,最小值为 1,最大值为 8),这是因为:

  • 一个数 a 加上负数的结果比 a 更小;
  • 一个数 a 加上 0 的结果不会比 a 更大;

而子问题的定义必须以一个数结尾,因此如果子问题 i的结果是负数或者 0 ,那么子问题 i + 1 的答案就是以 nums[i] 结尾的那个数。

因为我们把子问题定义得更清楚,子问题之间的联系就容易观察到。这是我们定义子问题、定义状态的经验。

接下来我们按照编写动态规划题解的步骤,把「状态定义」「状态转移方程」「初始化」「输出」「是否可以空间优化」全都写出来。

定义状态(定义子问题)

dp[i]:表示以 nums[i] 结尾的连续子数组的最大和。

说明:「结尾」和「连续」是关键字。

状态转移方程(描述子问题之间的联系)

根据状态的定义,由于 nums[i] 一定会被选取,并且以 nums[i] 结尾的连续子数组与以 nums[i - 1] 结尾的连续子数组只相差一个元素 nums[i]

假设数组 nums 的值全都严格大于 0 ,那么一定有 dp[i] = dp[i - 1] + nums[i]

可是 dp[i - 1] 有可能是负数,于是分类讨论:

  • 如果 dp[i - 1] > 0,那么可以把 nums[i] 直接接在 dp[i - 1] 表示的那个数组的后面,得到和更大的连续子数组;
  • 如果 dp[i - 1] ≤ 0,那么 nums[i] 加上前面的数 dp[i - 1] 以后值不会变大。于是 dp[i] 「另起炉灶」,此时单独的一个 nums[i] 的值,就是 dp[i]

以上两种情况的最大值就是 dp[i] 的值,写出如下状态转移方程:


dp[i] = {
  dp[i - 1] + nums[i],if dp[i - 1] > 0
  nums[i],            if dp[i - 1] ≤ 0
}

记为「状态转移方程 1」。

状态转移方程还可以这样写,反正求的是最大值,也不用分类讨论了,就这两种情况,取最大即可,因此还可以写出状态转移方程如下:


dp[i] = max(nums[i], dp[i - 1] + nums[i])

记为「状态转移方程 2」。

思考初始值

dp[0] 根据定义,只有 1 个数,一定以 nums[0] 结尾,因此 dp[0] = nums[0]

思考输出

注意:

  • 这里状态的定义不是题目中的问题的定义,不能直接将最后一个状态返回回去;因为如果出现一个极大的负数,最大值是在前半部分的

    这个问题的输出是把所有的 dp[0]dp[1]、……、dp[n - 1] 都看一遍,取最大值。

代码

理解版本
public class dp1 {
    public int maxArray(int nums[]) {
        int len = nums.length; // 获取数组长度
        int[] dp = new int[len]; // 创建一个与原数组相同长度的数组,用于存储动态规划过程中的最大和
        dp[0] = nums[0]; // 初始化动态规划数组的第一个值为原数组的第一个值

        // 开始动态规划过程
        for (int i = 1; i < len; i++) {
            if (dp[i - 1] > 0) { // 如果前一个位置的最大和大于0
                dp[i] = dp[i - 1] + nums[i]; // 则当前位置的最大和为前一个位置的最大和加上当前值
            } else {
                dp[i] = nums[i]; // 否则,当前位置的最大和为当前值本身
            }
        }

        int ans = dp[0]; // 初始化最终结果为动态规划数组的第一个值

        // 寻找动态规划数组中的最大值作为结果
        for (int i = 1; i < len; i++) {
            ans = Math.max(ans, dp[i]); // 更新最终结果为当前最大值与之前结果的较大值
        }

        return ans; // 返回最大连续子数组和
    }


    public static void main(String[] args) {
        dp1 solution = new dp1();

        int[] nums1 = {1, -2, 3, 10, -4, 7, 2, -5};
        System.out.println("最大连续子数组的和为: " + solution.maxArray(nums1)); // 输出: 18 (从数组索引2到索引6的子数组和为18)

        int[] nums2 = {-2, -3, -4, -1, -2, -1, -5, -3};
        System.out.println("最大连续子数组的和为: " + solution.maxArray(nums2)); // 输出: -1 (单个元素的子数组最大和为-1)

        int[] nums3 = {1, 2, 3, 4, 5};
        System.out.println("最大连续子数组的和为: " + solution.maxArray(nums3)); // 输出: 15 (整个数组的和为15)
    }
}
优化版本
public class Solution {

    public int maxSubArray(int[] nums) {
        int pre = 0;
        int res = nums[0];
        for (int num : nums) {
            pre = Math.max(pre + num, num);
            res = Math.max(res, pre);
        }
        return res;
    }
}

标签:最大,nums,09,问题,连续,数组,初探,100,dp
From: https://blog.csdn.net/qq_45103836/article/details/136933018

相关文章

  • C++U6-09 - 数学专题(二)各种进制知识
    学习目标 进制  二进制转十进制 二进制 代码 十进制转二进制代码 十进制转二进制小数方式,转其他进制同理 二进制转八进制方法二 八进制转二进制方法二二进制转十六进制方法二 代码 代码 十六进制转换成二进制 n进制转十进制小数部分......
  • 2099.整除的尾数
    importjava.util.LinkedHashMap;importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);while(true){LinkedHashMap<String,Integer>hashMap=newL......
  • 力扣HOT100 - 49. 字母异位词分组
    解题思路:排序注意:返回时不能用List,因为List是抽象类,return的必须是List的具体实现,如ArrayListclassSolution{publicList<List<String>>groupAnagrams(String[]strs){Map<String,List<String>>map=newHashMap<>();for(Stringstr......
  • 【LeetCode 509 】斐波那契数
    题目描述原题链接:LeetCode.0509斐波那契数解题思路题目直接给出了公式,朴素解法可以直接用\(O(n)\)复杂度求出答案,可以看做是递归或动态规划的入门题;这里重点作为模板题来介绍矩阵快速幂技巧,讲一下\(O(log_2n)\)复杂度的解法:递推公式\(F(n)=F(n-1)+F(n-2)\),转换为矩......
  • 3121002754
    这个作业属于哪个课程<软件工程2024-双学位>这个作业要求在哪里<团队作业1——团队展示&选题>这个作业的目标团队协作完成团队展示和选题目录1.团队展示2.选题要求3.团队计划4.团队成员绩效评估方法:1.团队展示1.队名2.队员信息(姓名+学号)陈俊豪3121001738......
  • 100 天机器学习指南
    100天机器学习指南除了机器学习专栏,我们打算出另外一期专栏,叫做100天机器学习指南,目标是通过100天的深入持续学习,让我们没有机器学习经验的人,也可以从事简单的机器学习工作,为职业生涯寻找增长点,专栏的主要特点如下:从0到1覆盖面广有实战第1–10天:线性代数机器学习......
  • 09 事务和连接池
    文章目录properties文件连接池service层实现类dao层实现类dao层实现类连接池类:创建线程池静态常量,用于放连接。创建Properties静态常量,用于解析properties文件静态代码块中,解析properties文件,将解析结果用于创建连接池连接方法:用线程获取连接,若没有,从连接池......
  • 【新品播报】米尔电子发布基于海思Hi3093高性能MPU产品
    新品播报!米尔电子发布了基于海思Hi3093高性能MPU的MYC-LHi3093核心板及开发板,此款核心板支持openEulerembeddedOS欧拉系统,丰富生态,可实现100%全国产自主可控。不仅如此,米尔基于Hi3093的核心板及开发板,配套提供工业控制demo,方便客户评估PLC等应用场景实时控制性能,为追求实时性......
  • k8s证书监控--x509-certificate-exporter
    目录k8s证书监控--x509-certificate-exporter一、下载并解压二、推送镜像到镜像仓库三、根据实际情况修改values.yaml,其他配置可不做修改四、配置监控以及告警五、异常处理k8s证书监控--x509-certificate-exporter一、下载并解压下载并解压helm包x509-certificate-exporter-3.1......
  • 海思 SS927V100 HI3519AV200 简介
    海思SS927V100HI3519AV200简介HI3519AV200是一颗专业ultra-HDSmartIPCameraSOC。SS927V100(另称:22AP70、SD3402)功能以及封装与HI3519AV200完全一致,可以平替HI3519AV200。最高支持四路sensor输入,支持最高4K60的ISP图像处理能力,支持3FWDR、多级降噪、六轴......