【每日一题】1186. 删除一次得到子数组最大和

这篇具有很好参考价值的文章主要介绍了【每日一题】1186. 删除一次得到子数组最大和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1186. 删除一次得到子数组最大和

题目描述

给你一个整数数组,返回它的某个 非空 子数组(连续元素)在执行一次可选的删除操作后,所能得到的最大元素总和。换句话说,你可以从原数组中选出一个子数组,并可以决定要不要从中删除一个元素(只能删一次哦),(删除后)子数组中至少应当有一个元素,然后该子数组(剩下)的元素总和是所有子数组之中最大的。

注意,删除一个元素后,子数组 不能为空。

示例 1:

输入:arr = [1,-2,0,3]
输出:4

解释:我们可以选出 [1, -2, 0, 3],然后删掉 -2,这样得到 [1, 0, 3],和最大。

示例 2:

输入:arr = [1,-2,-2,3]
输出:3
解释:我们直接选出 [3],这就是最大和。

示例 3:

输入:arr = [-1,-1,-1,-1]
输出:-1
解释:最后得到的子数组不能为空,所以我们不能选择 [-1] 并从中删去 -1 来得到 0。
     我们应该直接选择 [-1],或者选择 [-1, -1] 再从中删去一个 -1。

提示:

1 <= arr.length <= 105
-104 <= arr[i] <= 104

解题思路

思路:动态规划。dp[i][k]表示以arr[i]结尾的子数组删除k个元素的最大元素和,初始时dp[0][0]=arr[0],dp[0][1]=0,由于不能删除后为空元素,故res初始为dp[0][0]。dp[i][0]表示以arr[i]结尾的子数组删除0个元素的最大元素和,即将问题转化为最大连续子数组元素和,递推公式为dp[i][0]=max(dp[i-1][0],0)+arr[i],即dp[i-1][0]小于0则直接取arr[i];dp[i][1]表示以arr[i]结尾的子数组删除1个元素的最大元素和,递推公式为dp[i][1]=max(dp[i-1][0],dp[i-1][1]+arr[i]),即是删除第i个或者前面删除一个。

class Solution 
{
public:
    int maximumSum(vector<int>& arr) 
    {
        //dp[i][k]表示以arr[i]结尾的子数组删除k个元素的最大元素和
        int n=arr.size();
        vector<vector<int>> dp(n,vector<int>(2,0));
        dp[0][0]=arr[0];
        dp[0][1]=0;
        //不能为空数组
        int res=dp[0][0];
        for(int i=1;i<n;i++)
        {
            //删除0个即是最大连续子序列和 即dp[i-1][0]小于0则直接取arr[i]
            dp[i][0]=max(dp[i-1][0],0)+arr[i];
            //删除1个即是删除第i个或者前面删除一个
            dp[i][1]=max(dp[i-1][0],dp[i-1][1]+arr[i]);
            //求最大
            res=max({res,dp[i][0],dp[i][1]});
        }
        return res;
    }
};

总结:一般动态规划的状态定义是按照题目所描述的定义,再根据定义去想状态转移。此处需要注意的一点是,dp[i][k]表示以arr[i]结尾的子数组删除k个元素的最大元素和,在想这个状态转移时,不要只局限于前一个状态和当前状态的关系,比如dp[i][1]表示以i为结尾的子数组删除一次,那么可以是删除arr[i]或者是以i-1为结尾的子数组删除一次,这个以i-1为结尾的子数组删除一次不一定就是删除arr[i-1],其是一个以此类推的关系。

扩展:空间优化。文章来源地址https://www.toymoban.com/news/detail-516659.html

class Solution {
public:
    int maximumSum(vector<int>& arr) {
        //dp[i][k]表示以arr[i]结尾的子数组删除k个元素的最大元素和
        int n=arr.size();
        int a=arr[0];
        int b=0;
        //不能为空数组
        int res=a;
        for(int i=1;i<n;i++)
        {
            //注意 b要用到原来的a 故b在前面
            //删除1个即是删除第i个或者前面删除一个
            b=max(a,b+arr[i]);
            //删除0个即是最大连续子序列和 即dp[i-1][0]小于0则直接取arr[i]
            a=max(a,0)+arr[i];
            //求最大
            res=max({res,a,b});
        }
        return res;
    }
};

到了这里,关于【每日一题】1186. 删除一次得到子数组最大和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode每日一题】410. 分割数组的最大值

    2024-1-21 410. 分割数组的最大值 思路:二分查找+贪心 利用二分查找法和贪心算法来求解将数组分割为m个非空连续子数组,使得每个子数组的和的最大值最小 首先,我们需要确定二分查找的左右边界。左边界 left 初始化为数组中的最大值,右边界 right 初始化为数组所有元素的

    2024年01月23日
    浏览(39)
  • 【每日一题】数组中两个数的最大异或值

    【哈希集合】【位运算-异或和】【数组】【2023-11-04】 421. 数组中两个数的最大异或值 找出数组中两个数的最大异或结果。 一看数据量达到了 1 0 5 10^5 1 0 5 ,那时间复杂度为 O ( n 2 ) O(n^2) O ( n 2 ) 的方法必定超时,因此需要去找 O ( n l o g n ) O(nlogn) O ( n l o g n ) 或者 O ( n ) O(n)

    2024年02月05日
    浏览(47)
  • ( 数组和矩阵) 485. 最大连续 1 的个数 ——【Leetcode每日一题】

    难度:简单 给定一个二进制数组 nums , 计算其中最大连续 1 的个数。 示例 1: 输入:nums = [1,1,0,1,1,1] 输出:3 解释:开头的两位和最后的三位都是连续 1 ,所以最大连续 1 的个数是 3. 示例 2: 输入:nums = [1,0,1,1,0,1] 输出:2 提示: 1 = n u m s . l e n g t h = 1 0 5 1 = nums.length = 10^5

    2024年02月08日
    浏览(46)
  • 04-26 每日一题 1031. 两个非重叠子数组的最大和 学习反思

    1031. 两个非重叠子数组的最大和 考虑一个问题,如何求得数组中两个数的最大和。 可以固定一个数,然后向右遍历 如下,可以求得目标数组中两个数的最大和为 15 实现过程,如上图所示过程,右指针在移动过程中是跟随数组下标的 左边部分的元素需要维护一个最大值,所

    2023年04月27日
    浏览(42)
  • (动态规划) 剑指 Offer 42. 连续子数组的最大和 ——【Leetcode每日一题】

    难度:简单 输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为 O(n) 。 示例1: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 提示 : 1 = a r r . l e n g t h = 1 0 5 1 = arr.length = 10^

    2024年02月11日
    浏览(53)
  • 每日一题——删除最短的子数组使剩余数组有序(3.25)

    class Solution { public:     int findLengthOfShortestSubarray(vectorint arr) {         int len = arr.size();         if(len == 1)             return 0;         int left = 0;         int count = len - 1;         for (int i = 0; i  len - 1; ++i) {             if 

    2023年04月08日
    浏览(36)
  • 【每日一题】2.LeetCode——删除有序数组中的重复项

    📚博客主页:爱敲代码的小杨. ✨专栏:《Java SE语法》 ❤️感谢大家点赞👍🏻收藏⭐评论✍🏻,您的三连就是我持续更新的动力❤️ 🙏小杨水平有限,欢迎各位大佬指点,相互学习进步! 给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元

    2024年02月19日
    浏览(50)
  • 每日一题411数组中两个数的最大异或值(哈希表、前缀树:实现前缀树)

    LeetCode题目:https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/   本题使用哈希表方法主要运用到一个定理:异或满足算法交换律。即如果a^b = c,那么必然 b ^ c = a。且数组中的元素都在 [ 0 , 2 31 ) [0,2^{31}) [ 0 , 2 31 ) ,因此可以确定数值的最高位是30位。   因此,可以假设

    2024年02月05日
    浏览(42)
  • 【力扣每日一题】2023.8.8 任意子数组和的绝对值的最大值

    目录 题目: 示例: 分析: 代码: 题目给我们一个数组,让我们找出它的绝对值最大的子数组的和。 这边的子数组是要求连续的,让我们找出一个元素之和的绝对值最大的连续子数组。 要绝对值最大,那么就是两种情况,最大的正数以及最小的负数,所以我们可以兵分两路

    2024年02月13日
    浏览(44)
  • 【算法】【Python3、动态规划、贪心、二分查找】力扣1671. 得到山形数组的最少删除次数

    1671. 得到山形数组的最少删除次数 给定一个整数数组 nums ,我们定义该数组为山形数组当且仅当: nums 的长度至少为 3。 存在一个下标 i 满足 0 i len(nums) - 1 且: nums[0] nums[1] ... nums[i - 1] nums[i] nums[i] nums[i + 1] ... nums[len(nums) - 1] 现在,给定整数数组 nums ,我们的目标是将其变为

    2024年01月18日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包