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 <= 105
• 1 <= nums[i] <= 106

思路

从后往前遍历数组，设置一个迭代变量res，如果res>=nums[i],则迭代变量res+=nums[i]，否则res=nums[i]，在遍历过程中更新ans

这种遍历迭代的思路为什么是正确的呢？

1. 因为在逆序遍历的过程中可以保证记录到每次连续合并的最大值
2. res=nums[i]可以理解为每次连续合并的第一个数(最开始res=nums[n-1])，遍历过程中如果res>=nums[i]，则res+=nums[i]，这样可以保证每次连续合并的数的值尽可能大
3. 当res<nums[i]时，res重置为nums[i] (即res又变为新一轮连续合并的第一个数)

代码

碎碎念：这短短的十几行代码是我这个菜鸡在比赛的时候坐牢近1h才想出来的，仅以此篇题解记录自己的菜鸡生涯

class Solution {
    public long maxArrayValue(int[] nums) {
        int n=nums.length;
        long ans=nums[n-1];
        long res=nums[n-1];
        for(int i=n-2;i>=0;i--){
            if(res>=nums[i]){
                res+=nums[i];
            }else{
                res=nums[i];
            }
            ans=Math.max(ans,res);
        }
        return ans;
    }
}

复杂度分析

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