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.
题目的意思是数组中的元素可以吞噬前面一个不大于自身的元素,当所有元素都无法吞噬时,返回数组中可以获得的元素的最大值.要想获得保留元素的最大值,理应最后数组内剩余的元素应尽量的少, 也就是尽量让所有元素都被吞噬, 那我们就不能从前往后遍历进行吞噬了,因为这样会导致当前元素本来可以被吞噬,但是因为吞噬了前方元素使得自身又不能被吞噬了,这样中最终数组中的保留元素有可能变多,使得答案不正确,
例如nums = [1,1,1].
本来应该是下标2吞噬下标1,在吞噬下标0,这样得的结果是[3]
但如果下标1先吞噬下标0,那么nums = [2,1],导致最终的结果不正确.
所以我们应该从后向前遍历进行吞噬,这样可以保证吞噬的元素最多,使得保留元素最少,遍历过程中不断更新当前吞噬元素sum,如果遇到无法吞噬元素, 则更新ans的最大值,sum更新为0.
最终实现代码如下:
1 class Solution { 2 public long maxArrayValue(int[] nums) { 3 long ans = -1, sum = 0; 4 for (int i = nums.length - 1; i > -1 ; i--) { 5 if (sum < nums[i]) { 6 ans = Math.max(ans, sum); 7 sum = 0; 8 } 9 sum += nums[i]; 10 } 11 return Math.max(ans, sum); 12 } 13 }
热门相关:中国惊奇先生:极道仙师 工作女郎 第八个嫌疑人 奇迹俱乐部 我女儿的爱人3