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

简介: 【力扣算法05】之 _1911_ 最大子序列交替和- 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] 不是。

示例 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

思路分析

  • 首先, 定义数组 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] 中的较大值,即为所求的交替元素和的最大值。

代码分析

代码实现了一个计算交替元素和的最大值的函数 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)

示例2

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

示例3

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

完结


目录
打赏
0
0
0
0
25
分享
相关文章
解锁文件共享软件背后基于 Python 的二叉搜索树算法密码
文件共享软件在数字化时代扮演着连接全球用户、促进知识与数据交流的重要角色。二叉搜索树作为一种高效的数据结构,通过有序存储和快速检索文件,极大提升了文件共享平台的性能。它依据文件名或时间戳等关键属性排序,支持高效插入、删除和查找操作,显著优化用户体验。本文还展示了用Python实现的简单二叉搜索树代码,帮助理解其工作原理,并展望了该算法在分布式计算和机器学习领域的未来应用前景。
Python入门:6.深入解析Python中的序列
在 Python 中,**序列**是一种有序的数据结构,广泛应用于数据存储、操作和处理。序列的一个显著特点是支持通过**索引**访问数据。常见的序列类型包括字符串(`str`)、列表(`list`)和元组(`tuple`)。这些序列各有特点,既可以存储简单的字符,也可以存储复杂的对象。 为了帮助初学者掌握 Python 中的序列操作,本文将围绕**字符串**、**列表**和**元组**这三种序列类型,详细介绍其定义、常用方法和具体示例。
Python入门:6.深入解析Python中的序列
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
24 12
基于 Python 的布隆过滤器算法在内网行为管理中的应用探究
在复杂多变的网络环境中,内网行为管理至关重要。本文介绍布隆过滤器(Bloom Filter),一种高效的空间节省型概率数据结构,用于判断元素是否存在于集合中。通过多个哈希函数映射到位数组,实现快速访问控制。Python代码示例展示了如何构建和使用布隆过滤器,有效提升企业内网安全性和资源管理效率。
28 9
内网桌面监控软件深度解析:基于 Python 实现的 K-Means 算法研究
内网桌面监控软件通过实时监测员工操作,保障企业信息安全并提升效率。本文深入探讨K-Means聚类算法在该软件中的应用,解析其原理与实现。K-Means通过迭代更新簇中心,将数据划分为K个簇类,适用于行为分析、异常检测、资源优化及安全威胁识别等场景。文中提供了Python代码示例,展示如何实现K-Means算法,并模拟内网监控数据进行聚类分析。
30 10
|
27天前
|
控制局域网上网软件之 Python 字典树算法解析
控制局域网上网软件在现代网络管理中至关重要,用于控制设备的上网行为和访问权限。本文聚焦于字典树(Trie Tree)算法的应用,详细阐述其原理、优势及实现。通过字典树,软件能高效进行关键词匹配和过滤,提升系统性能。文中还提供了Python代码示例,展示了字典树在网址过滤和关键词屏蔽中的具体应用,为局域网的安全和管理提供有力支持。
52 17
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
基于遗传优化算法的风力机位置布局matlab仿真
本项目基于遗传优化算法(GA)进行风力机位置布局的MATLAB仿真,旨在最大化风场发电效率。使用MATLAB2022A版本运行,核心代码通过迭代选择、交叉、变异等操作优化风力机布局。输出包括优化收敛曲线和最佳布局图。遗传算法模拟生物进化机制,通过初始化、选择、交叉、变异和精英保留等步骤,在复杂约束条件下找到最优布局方案,提升风场整体能源产出效率。
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
149 68

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等