求解LeetCode题库第2789题合并后数组中的最大元素

本文主要是介绍求解LeetCode题库第2789题合并后数组中的最大元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

难度：中等

问题描述：

给你一个下标从 0 开始、由正整数组成的数组 nums 。

你可以在数组上执行下述操作任意次：

选中一个同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] 的整数 i 。

将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ，并从数组中删除元素 nums[i] 。

返回你可以从最终数组中获得的最大元素的值。

示例 1：

输入：nums = [2,3,7,9,3]

输出：21

解释：我们可以在数组上执行下述操作：

- 选中 i = 0 ，得到数组 nums = [5,7,9,3] 。

- 选中 i = 1 ，得到数组 nums = [5,16,3] 。

- 选中 i = 0 ，得到数组 nums = [21,3] 。

最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。

示例 2：

输入：nums = [5,3,3]

输出：11

解释：我们可以在数组上执行下述操作：

- 选中 i = 1 ，得到数组 nums = [5,6] 。

- 选中 i = 0 ，得到数组 nums = [11] 。

最终数组中只有一个元素，即 11 。

分析：

问题并不复杂，试过之后，才知道在寻找“同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] ”的整数 i 时，如果从nums的左边向右寻找时，就会漏掉一部分处理元素，使得最后从nums中得不到的真正的最大整数，无法完成问题的求解，正确的做法是从nums的右端向左端开始寻找。

程序设计了一个函数hbone（nums），从nums的右端向左端寻找，如果找到满足条件的整数i，返回可以继续处理的标志Fasle和处理之后的nums，否则返回不能继续处理的标志True和没有处理的nums。

程序如下：

#在nums中从最右边向左查找
def hbone(nums):n=len(nums)temp=[]for i in range(1,n):if nums[-i]>=nums[-(i+1)]:temp.append(i)breakif temp==[]:return True,numselse:i=temp[0]nums[-i]=nums[-i]+nums[-(i+1)]del nums[-(i+1)]return False,numsnums=eval(input('nums='))
while True:a,b=hbone(nums)print(a,b)nums=b[:]if a:print(max(b))break

运行实例1

nums=[3,4,7,6,8,1,2]

False [3, 4, 7, 6, 8, 3]

False [3, 4, 7, 14, 3]

False [3, 4, 21, 3]

False [3, 25, 3]

False [28, 3]

True [28, 3]

运行实例2

nums=[2,3,7,9,3]

False [2, 3, 16, 3]

False [2, 19, 3]