【力扣算法05】之 _1911_ 最大子序列交替和- python

这篇具有很好参考价值的文章主要介绍了【力扣算法05】之 _1911_ 最大子序列交替和- python。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

问题描述

【力扣算法05】之 _1911_ 最大子序列交替和- python,python案例分析归纳,算法,leetcode,python,动态规划,最大交替和,力扣算法,python面试刷题

一个下标从 0 开始的数组的 交替和 定义为 偶数 下标处元素之 和 减去 奇数 下标处元素之 和 。 比方说,数组 [4,2,5,3] 的交替和为 (4 + 5) - (2 + 3) = 4 。
给你一个数组 nums ,请你返回 nums 中任意子序列的 最大交替和 (子序列的下标 重新 从 0 开始编号)。 一个数组的 子序列 是从原数组中删除一些元素后(也可能一个也不删除)剩余元素不改变顺序组成的数组。比方说,[2,7,4] 是 [4,2,3,7,2,1,4] 的一个子序列(加粗元素),但是 [2,4,2] 不是。
【力扣算法05】之 _1911_ 最大子序列交替和- python,python案例分析归纳,算法,leetcode,python,动态规划,最大交替和,力扣算法,python面试刷题

示例 1

输入:nums = [4,2,5,3]
输出:7
解释:最优子序列为 [4,2,5] ,交替和为 (4 + 5) - 2 = 7 。

示例2

输入:nums = [5,6,7,8]
输出:8
解释:最优子序列为 [8] ,交替和为 8 。

示例3

输入:nums = [6,2,1,2,4,5]
输出:10
解释:最优子序列为 [6,1,5] ,交替和为 (6 + 5) - 1 = 10 。

提示

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

思路分析

【力扣算法05】之 _1911_ 最大子序列交替和- python,python案例分析归纳,算法,leetcode,python,动态规划,最大交替和,力扣算法,python面试刷题

  • 首先, 定义数组 dp0 和 dp1,长度都为 n,并将它们初始化为全零数组。dp0[i] 表示从 nums[0] 到 nums[i] 的子数组中,以 nums[i] 结尾的交替和的最大值;dp1[i] 表示从 nums[0] 到 nums[i] 的子数组中,以 nums[i] 结尾的交替和末尾为正数的最大值。

  • 然后,我们开始迭代遍历数组 nums,从索引 1 开始。在每次迭代中,我们根据以下公式更新 dp0 和 dp1 的值:

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

  • 对于 dp0[i],我们有两个选择:要么不选择当前元素 nums[i],即交替和不变;要么将前一个交替和末尾的正数减去当前元素 nums[i],以得到更大的交替和。所以,dp0[i] 的值可以通过比较 dp0[i-1] 和 dp1[i-1] - nums[i] 的大小来确定,取其中较大的值作为 dp0[i] 的结果。

  • 对于 dp1[i],同样有两个选择:要么不选择当前元素 nums[i],即交替和末尾为正数的最大值不变;要么将前一个交替和末尾的负数加上当前元素 nums[i],以得到更大的交替和。所以,dp1[i] 的值可以通过比较 dp1[i-1] 和 dp0[i-1] + nums[i] 的大小来确定,取其中较大的值作为 dp1[i] 的结果。

  • 通过不断更新 dp0 和 dp1 数组的值,我们就可以得到从 nums[0] 到 nums[i] 的子数组中,以 nums[i] 结尾的交替和的最大值和交替和末尾为正数的最大值。

  • 最后, 返回 dp0[n - 1] 和 dp1[n - 1] 中的较大值,即为所求的交替元素和的最大值。

代码分析

【力扣算法05】之 _1911_ 最大子序列交替和- python,python案例分析归纳,算法,leetcode,python,动态规划,最大交替和,力扣算法,python面试刷题

代码实现了一个计算交替元素和的最大值的函数 maxAlternatingSum

class Solution(object):
    def maxAlternatingSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

首先,这是一个名为 Solution 的类定义,它实现了一个方法 maxAlternatingSum。该方法接受一个参数 nums,它是一个整数列表,并且返回一个整数作为结果。

n = len(nums)
dp0 = [0] * n
dp1 = [0] * n

接下来,通过获取数组 nums 的长度 n,创建了两个与 nums 相同长度的全零数组 dp0dp1,用于存储中间计算的结果。

dp1[0] = nums[0]  # 初始化

dp1 的首元素设置为 nums 的首元素,作为初始值。

for i in range(1, n):
    dp0[i] = max(dp0[i - 1], dp1[i - 1] - nums[i])
    dp1[i] = max(dp1[i - 1], dp0[i - 1] + nums[i])

然后,使用一个循环从索引 1 开始遍历数组 nums,对每个位置 i 进行动态规划计算。根据之前解释的公式,更新 dp0[i]dp1[i] 的值。

return max(dp0[n - 1], dp1[n - 1])

最后,返回 dp0dp1 中的最大值作为结果。

代码的核心思想是使用动态规划来求解交替元素和的最大值。通过迭代计算并更新 dp0dp1 数组中的值,最终得到结果。

完整代码

class Solution(object):
    def maxAlternatingSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 创建Solution类,定义maxAlternatingSum方法,该方法接受整数列表nums作为参数,返回一个整数作为结果

        n = len(nums)
        # 获取整数列表nums的长度,即列表中元素的数量

        dp0 = [0] * n
        dp1 = [0] * n
        # 创建两个初始长度为n的全零列表dp0和dp1,用于记录中间计算结果

        dp1[0] = nums[0]
        # 将dp1列表的第一个元素设置为nums列表的第一个元素,作为初始化值

        for i in range(1, n):
            # 循环从索引1开始遍历整数列表nums

            dp0[i] = max(dp0[i - 1], dp1[i - 1] - nums[i])
            # 在位置i不选择当前元素时,最大交替和为前一个位置不选择元素的最大交替和dp0[i-1]和dp1[i-1]减去当前元素nums[i]的较大值

            dp1[i] = max(dp1[i - 1], dp0[i - 1] + nums[i])
            # 在位置i选择当前元素时,最大交替和为前一个位置选择元素的最大交替和dp1[i-1]和dp0[i-1]加上当前元素nums[i]的较大值

        return max(dp0[n - 1], dp1[n - 1])
        # 返回dp0和dp1列表中最后一个元素的较大值作为结果,即表示在最后一个位置不选择当前元素和选择当前元素两种情况下的最大交替和

运行示例代码

示例1

nums = [4, 2, 5, 3]
solution = Solution()
result = solution.maxAlternatingSum(nums)
print(result)

【力扣算法05】之 _1911_ 最大子序列交替和- python,python案例分析归纳,算法,leetcode,python,动态规划,最大交替和,力扣算法,python面试刷题

示例2

nums = [5,6,7,8]
solution = Solution()
result = solution.maxAlternatingSum(nums)
print(result)

【力扣算法05】之 _1911_ 最大子序列交替和- python,python案例分析归纳,算法,leetcode,python,动态规划,最大交替和,力扣算法,python面试刷题

示例3

nums = [6,2,1,2,4,5]
solution = Solution()
result = solution.maxAlternatingSum(nums)
print(result)

【力扣算法05】之 _1911_ 最大子序列交替和- python,python案例分析归纳,算法,leetcode,python,动态规划,最大交替和,力扣算法,python面试刷题

完结

【力扣算法05】之 _1911_ 最大子序列交替和- python,python案例分析归纳,算法,leetcode,python,动态规划,最大交替和,力扣算法,python面试刷题文章来源地址https://www.toymoban.com/news/detail-552000.html

到了这里,关于【力扣算法05】之 _1911_ 最大子序列交替和- python的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【算法设计与分析】(三)动态规划_更新中:斐波那契、二项式系数、树的最大独立集、最长递增、公共子序列、编辑距离、Hischberg、最优二叉搜索树、交替拿硬币、石子合并、背包、乘电梯

    分治 动态规划本篇 还差一堆 贪心 网络流 首先,怕误人子弟必须声明一下 本人很菜 (越复习越觉得完蛋了 作为一个科班研究生算法学成这样非常惭愧(跪 ,可能写的都不是很懂,很多内容打算背过去了。因为我发现好像真的有人看所以多提醒一句。。(大家就只食用目录

    2024年01月19日
    浏览(98)
  • leetcode刷题(轮转数组、买股票的最佳时机、买卖股票的最佳时机2、跳跃游戏、跳跃游戏2、最大子序列交替和、交替数字和、下降路径最小和)

    目录 1、轮转数组 2、买卖股票的最佳时机 3、买卖股票的最佳时机② 4、跳跃游戏 5、跳跃游戏2 6、最大子序列交替和 7、交替数字和 8、下降路径最小和 1、轮转数组 2、买卖股票的最佳时机 3、买卖股票的最佳时机② 4、跳跃游戏 5、跳跃游戏2 6、最大子序列交替和 7、交替数

    2024年02月16日
    浏览(32)
  • Python数据分析案例05——影响经济增长的因素(随机森林回归)

    在计量经济学里面的研究,围绕着影响GDP的因素的研究有很多,基本都是做回归,拿GDP作为被解释变量y,其他因素作为解释变量x。然后做线性回归,时间序列就做自回归,面板数据就做固定效应等等。本次案例采用机器学习里面的随机森林回归来研究影响经济增长的因素,

    2024年02月09日
    浏览(43)
  • 【算法思考记录】动态规划入门!力扣2606. 找到最大开销的子字符串【Python3、动态规划】

    原题链接 动态规划(Dynamic Programming,简称 DP)是一种通过将原问题分解为相互重叠的子问题并只解决一次的方法来解决问题的算法优化技术。动态规划通常用于优化递归问题,通过存储子问题的解来避免重复计算,从而显著提高算法的效率。 动态规划的基本思想是将原问题

    2024年02月03日
    浏览(44)
  • Python时间序列分析--ARIMA模型实战案例

    **本文将介绍使用Python来完成时间序列分析ARIMA模型的完整步骤与流程,绘制时序图,平稳性检验,单位根检验,白噪声检验,模型定阶,参数估计,模型检验等完整步骤。Python建立时间序列分析–ARIMA模型实战案例 时间序列指的是将带有同一指标单位的数值按照产生时间的先

    2024年01月17日
    浏览(50)
  • Python数据分析案例11——灰色预测法预测时间序列数据

    本次案例来自2022华为杯第E题,第2小问。给定了2012.01-2022.03的土壤湿度的月度数据,需要预测2022.04-2023.12的土壤湿度的月度数据。典型的时间序列预测。 传统的时间序列预测肯定是ARIMA模型,可以参考我之前的文章。Python统计学10——时间序列分析自回归模型(ARIMA) 现在流行的

    2024年02月06日
    浏览(62)
  • 【算法详解】力扣179.最大数

    力扣链接:力扣179.最大数 给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。 注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。 示例 1: 输入:nums = [10,2] 输出:“210” 可使用 贪心策略 ,只要每一步都保证是

    2024年01月19日
    浏览(33)
  • Python数据分析案例42——基于Attention-BiGRU的时间序列数据预测

    承接上一篇的学术缝合,排列组合模型,本次继续缝合模型演示。 Python数据分析案例41——基于CNN-BiLSTM的沪深300收盘价预测-CSDN博客 虽然我自己基于各种循环神经网络做时间序列的预测已经做烂了.....但是还是会有很多刚读研究生或者是别的领域过来的小白来问这些神经网络

    2024年04月15日
    浏览(40)
  • dp算法 力扣152乘积最大子数组

    本文是Java代码!! 152. 乘积最大子数组 - 力扣(LeetCode) 给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整数。 子数组 是数组的连续子序列。 示例 1: 输入

    2024年02月13日
    浏览(42)
  • 【力扣每日一题】力扣2765最长交替子数组

    力扣2765最长交替子数组 给你一个下标从 0 开始的整数数组 nums 。如果 nums 中长度为 m 的子数组 s 满足以下条件,我们称它是一个 交替子数组 : m  大于  1  。  s1  =  s0  +  1  。 下标从  0  开始的子数组  s  与数组 [ s0 ,  s1 ,  s0 ,  s1 ,..., s(m-1) % 2 ] 一样。也就是说,

    2024年01月24日
    浏览(52)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包