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 。

提示：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6

---

解题分析及思路：

方法：贪心

思路：

本题可以使用贪心+逆向思维的方式解决。

我们可以从数组的最后一个元素开始，向前遍历数组，如果当前元素大于等于前一个元素，我们就将前一个元素的值加到当前元素上，并将前一个元素的值置为0。

最后我们遍历数组，找到最大的元素即可。

func maxArrayValue(nums []int) int64 {
	for i := len(nums) - 1; i > 0; i-- {
		if nums[i] >= nums[i-1] {
			nums[i-1] += nums[i]
			nums[i] = 0
		}
	}
	var result = nums[len(nums)-1]
	for i := range nums {
		if nums[i] > result {
			result = nums[i]
		}
	}
	return int64(result)
}

复杂度：

• 时间复杂度：O(N)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:117 ms,击败了10.71% 的Go用户
• 内存消耗:9.3 MB,击败了10.71% 的Go用户