Leetcode 3026. Maximum Good Subarray Sum

2024-02-04 23:44

本文主要是介绍Leetcode 3026. Maximum Good Subarray Sum,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  • Leetcode 3026. Maximum Good Subarray Sum
    • 1. 解题思路
    • 2. 代码实现
  • 题目链接:3026. Maximum Good Subarray Sum

1. 解题思路

这一题的话主要就是要快速遍历所有的good subarray并快速获得每一个good subarray的和的最大值。

因此,问题就主要就成了两个问题:

  1. 如何快速找到所有的good subarray
  2. 对任意一个good subarray,如何快速求得其和

对于第二个问题,我们只需要用累积数组即可求得,对于任意一个已知首尾的subarray,我们将累积数组相减即可得到其对应的subarray的元素之和。

而对于第一个问题,我们只需要记录一下所有之前元素作为起始坐标时的位置即可。

更进一步地,由于我们只需要计算和的最大值,因此对于任意相同的元素作为开始坐标时,我们只需要保留其前部元素的最小值即可。

2. 代码实现

给出python代码实现如下:

class Solution:def maximumSubarraySum(self, nums: List[int], k: int) -> int:cumsums = list(accumulate(nums, initial=0))ans = -math.inf_min= {}def get_max_sub(s, tgt):return s - _min.get(tgt, math.inf)for i, x in enumerate(nums):s = cumsums[i+1]ans = max(ans, get_max_sub(s, x-k), get_max_sub(s, x+k))_min[x] = min(_min.get(x, math.inf), s-x)return ans if ans != -math.inf else 0

提交代码评测得到:耗时1093ms,占用内存30.6MB。

这篇关于Leetcode 3026. Maximum Good Subarray Sum的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/679152

相关文章

PyTorch中cdist和sum函数使用示例详解

《PyTorch中cdist和sum函数使用示例详解》torch.cdist是PyTorch中用于计算**两个张量之间的成对距离(pairwisedistance)**的函数,常用于点云处理、图神经网... 目录基本语法输出示例1. 简单的 2D 欧几里得距离2. 批量形式(3D Tensor)3. 使用不

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

最大流=最小割=最小点权覆盖集=sum-最大点权独立集

二分图最小点覆盖和最大独立集都可以转化为最大匹配求解。 在这个基础上,把每个点赋予一个非负的权值,这两个问题就转化为:二分图最小点权覆盖和二分图最大点权独立集。   二分图最小点权覆盖     从x或者y集合中选取一些点,使这些点覆盖所有的边,并且选出来的点的权值尽可能小。 建模:     原二分图中的边(u,v)替换为容量为INF的有向边(u,v),设立源点s和汇点t

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param