04-26 每日一题 1031. 两个非重叠子数组的最大和 学习反思

这篇具有很好参考价值的文章主要介绍了04-26 每日一题 1031. 两个非重叠子数组的最大和 学习反思。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1031. 两个非重叠子数组的最大和

类似问题转换

  1. 考虑一个问题,如何求得数组中两个数的最大和。
    1. 可以固定一个数,然后向右遍历
    2. 如下,可以求得目标数组中两个数的最大和为 15

04-26 每日一题 1031. 两个非重叠子数组的最大和 学习反思

把思路实现为代码

  1. 实现过程,如上图所示过程,右指针在移动过程中是跟随数组下标的
  2. 左边部分的元素需要维护一个最大值,所以需要一个变量,保存左边元素的最大值
  3. 需要求得最大和,所以需要一个变量保存最终结果
  4. 最后一次遍历即可
def two_sum_max(nums: List[int]) -> int:
    ans, left = 0, 0
    for i in range(1, len(nums)):
        left = max(left, nums[i-1])
        ans = max(ans, left + nums[i])
    return ans

回到本题

  1. 扩展数字到区间,求数组内两个不重叠的连续区间的和的最大值
  2. 可以使用同样的思路,如下图

04-26 每日一题 1031. 两个非重叠子数组的最大和 学习反思

思路实现为代码

  1. 首先最终返回一个最大值,需要一个变量保存最终结果
  2. 遍历过程中可以计算右边部分的区间和
    1. 涉及到区间和需要联想到数组前缀和
    2. 所以需要实现求得数组的前缀和
  3. 需要一个变量,在遍历过程中维护左边部分的最大值
    1. 最终结果=左边部分最大值+右边部分区间和
    2. 在遍历过程中不断比较得到最终结果
  4. 需要注意在遍历过程中求前缀和的时候的下标计算控制
def max_two_gap_of_nums(nums: List[int], first_len: int, second_len: int) -> int:
    n = len(nums)
    for i in range(1, n):
        nums[i] = nums[i - 1] + nums[i]
    ans, left_max = 0, 0
    # 给 右边区间留足空间  遍历到  n - second_len
    # 区间 second_len 在后
    for i in range(first_len, n - second_len + 1):
        # 维护左边窗口的最大值的和
        # i 从 first_len 开始遍历,所要求的区间和位于  first_len 前面
        # 所以 有  nums[i - 1] - nums[i - first_len - 1]
        # 又因为 i - first_len - 1 有可能小于0,所以需要额外判断
        left_max = max(left_max, nums[i - 1] - (0 if (i - first_len - 1 < 0) else nums[i - first_len - 1]))
        # 左区间最大值 + 右边区间的最大值
        ans = max(ans, left_max + nums[i + second_len - 1] - nums[i - 1])
    # 区间 first_len 在后
    left_max = 0
    for i in range(second_len, n - first_len + 1):
        left_max = max(left_max, nums[i - 1] - (0 if (i - second_len - 1 < 0) else nums[i - second_len - 1]))
        ans = max(ans, left_max + nums[i + first_len - 1] - nums[i - 1])
    return ans
  1. 优化
    1. 可以把 两个区间 依次排列在后面优化成一个方法
def better(nums: List[int], first_len: int, second_len: int) -> int:
    n = len(nums)
    for i in range(1, n):
        nums[i] = nums[i - 1] + nums[i]
    return max(two_gap_sum(nums, first_len, second_len), two_gap_sum(nums, second_len, first_len))


def two_gap_sum(nums: List[int], a: int, b: int) -> int:
    res, t = 0, 0
    for i in range(a, len(nums) - b + 1):
        t = max(t, nums[i-1] - (0 if (i - a - 1 < 0) else nums[i - a - 1]))
        res = max(res, t + nums[i + b - 1] - nums[i - 1])
    return res

极其优雅的一次遍历

  1. 上述思路都是分情况遍历数组两次
  2. 实现思路的核心思想是固定一个窗口,然后求另一个窗口的最大值。然后再固定另一个窗口,进行两次遍历求得最终结果
  3. 实际上该过程可以在一次遍历中搞定,如下图

04-26 每日一题 1031. 两个非重叠子数组的最大和 学习反思

def best_way(nums: List[int], a: int, b: int) -> int:
    n = len(nums)
    for i in range(1, n):
        nums[i] = nums[i] + nums[i - 1]
    res, left_max, right_max = nums[a + b - 1], nums[a - 1], nums[b - 1]
    for i in range(a+b, n):
        left_max = max(left_max, nums[i - b] - nums[i - a - b])
        right_max = max(right_max, nums[i - a] - nums[i - a - b])
        res = max(res, max(left_max + nums[i] - nums[i - b], right_max + nums[i] - nums[i - a]))
    return res

心得感悟

  1. 通过学习 **lee **神的算法学习分享,要注重以下几点
    1. 切忌不要以做很多很多题为目标
    2. 培养对算法的兴趣
    3. 坚持写题解
    4. 不要怕浪费时间,万丈高楼平地起,坚持就好

参考

https://leetcode.cn/problems/maximum-sum-of-two-non-overlapping-subarrays/solution/python3javacgotypescript-yi-ti-yi-jie-qi-7nqt/
https://leetcode.cn/problems/maximum-sum-of-two-non-overlapping-subarrays/solution/ying-wen-ban-shang-pai-ming-di-yi-de-fei-chang-jin/
https://leetcode.cn/problems/maximum-sum-of-two-non-overlapping-subarrays/solution/qian-zhui-he-bian-li-onshi-jian-fu-za-du-ji-ke-qiu/文章来源地址https://www.toymoban.com/news/detail-426845.html

到了这里,关于04-26 每日一题 1031. 两个非重叠子数组的最大和 学习反思的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • Leetcode每日一题——“合并两个有序数组”

    各位CSDN的uu们你们好呀,又到小雅兰的愉快题解时候啦,今天,我们的题目内容是合并两个有序数组,下面,让我们进入合并两个有序数组的世界吧 示例 1: 输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出:[1,2,2,3,5,6] 解释:需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [ 1,2

    2023年04月24日
    浏览(64)
  • 力扣每日一题88:合并两个有序数组

    给你两个按  非递减顺序  排列的整数数组  nums1   和  nums2 ,另有两个整数  m  和  n  ,分别表示  nums1  和  nums2  中的元素数目。 请你  合并   nums2   到  nums1  中,使合并后的数组同样按  非递减顺序  排列。 注意: 最终,合并后数组不应由函数返回,而是存储在

    2024年02月07日
    浏览(46)
  • 【LeetCode每日一题】53. 最大子数组和

    https://leetcode.cn/problems/maximum-subarray/description/ 给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组 是数组中的一个连续部分。 先算出数组的前缀和,然后通过2个for循环遍历出所有的连续子数组。 寻找一个具有

    2024年02月04日
    浏览(51)
  • C语言每日一题(22)合并两个有序数组

    力扣网 88. 合并两个有序数组 给你两个按  非递减顺序  排列的整数数组  nums1   和  nums2 ,另有两个整数  m  和  n  ,分别表示  nums1  和  nums2  中的元素数目。 请你  合并   nums2   到  nums1  中,使合并后的数组同样按  非递减顺序  排列。 注意: 最终,合并后数组

    2024年02月08日
    浏览(40)
  • 算法每日一题: 分割数组的最大值 | 动归 | 分割数组 | 贪心+二分

    Hello,大家好,我是星恒 呜呜呜,今天给大家带来的又是一道经典的动归难题。 题目:leetcode 410 给定一个非负整数数组 nums 和一个整数 k ,你需要将这个数组分成 k_ 个非空的连续子数组。 设计一个算法使得这 k _个子数组各自和的最大值最小。 示例: 示例 1: 示例 2: 示例

    2024年01月22日
    浏览(45)
  • 【LeetCode每日一题】410. 分割数组的最大值

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

    2024年01月23日
    浏览(38)
  • 【力扣每日一题】2023.8.13 合并两个有序数组

    目录 题目: 示例: 分析: 代码: 题目给我们两个升序数组,让我们合并它们,要求合并之后仍然是升序,并且这个合并操作是在数组1原地修改的。数组1的有效数据长度为 m ,而数组1的长度为 m + n,n 是数组2的有效数据长度以及数组的长度。 比较直观容易想到的做法就是

    2024年02月12日
    浏览(40)
  • 2023-08-13 LeetCode每日一题(合并两个有序数组)

    点击跳转到题目位置 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 **注意:**最终,合并后数组不应由函数返回,而是存储在数组 num

    2024年02月13日
    浏览(59)
  • 【每日一题】1186. 删除一次得到子数组最大和

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

    2024年02月11日
    浏览(31)
  • C语言每日一题:6.移除元素+合并两个有序数组。

    一:暴力查找的方法: 1.找到对应val值的下标,返回数组的下标。 2.删除对应的下标,从前向后用后面覆盖前面。当后一个是数组最后一个数值是就赋值结束了(注意数组越界的问题)。 3.删除了一个数之后数组元素个数要–。 4.查找和删除是在一个循环里面因为val的值可能

    2024年02月15日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包