目标
给你一个下标从 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
思路
这个题要我们对一个数组进行操作并返回最大的元素值。这里的操作指的是合并相邻的非严格递增元素。
刚开始没有头绪，如果真的按照操作步骤先把符合条件的值求出来，替换掉较大元素的值并删掉较小元素，那么就需要频繁地移动数组数据。
除此之外需要考虑一个重要的问题，如何合并才能使最终的结果最大？如果从前向后合并，比如 [2,6,7] 先合并前两个得到[8,7]肯定没有从后向前合并得到的值 [2, 13] [15] 大。是否存在那种先从前向后合并，然后再从后向前合并才能得到最大值的情况？
刚开始是不那么容易弄清的。也考虑过优先合并 后面的元素值 比 合并后的元素值 大的 元素，提前考虑了一步能否避免上面的情况？好像可以，因为操作没有破坏原数组能否合并的状态。那么这种操作需要循环几次？时间复杂度是O(n)~O(nlogn)吗？
[1,2,1,4,1,2,1,4]一次遍历后可以变为[3,5,3,5]，然后再遍历一次得到 [8, 8]，再来一次 [16]，即O(nlogn)。更好的情况就是递增序列O(n)。
经过上面的分析可以发现，优先使后面的元素最大才能得到最大值。那么为什么不从后向前遍历并累加呢？如果遇到一个元素的值比后面所有元素的累加和还要大，那不管前面怎么操作，由于元素都是正整数，合并后只会更大。
想清楚了这一点就非常简单了。
代码
/**
* @date 2024-03-14 11:29
*/
public class MaxArrayValue {
public long maxArrayValue(int[] nums) {
long res = nums[nums.length - 1];
for (int i = nums.length - 1; i >= 1; i--) {
res = res >= nums[i - 1] ? res + nums[i - 1] : nums[i - 1];
}
return res;
}
public static void main(String[] args) {
MaxArrayValue main = new MaxArrayValue();
// int[] nums = new int[]{2, 3, 7, 9, 3};
// int[] nums = new int[]{5, 3, 3};
// int[] nums = new int[]{77};
int[] nums = new int[]{34, 95, 50, 12, 25, 100, 21, 3, 25, 16, 76, 73, 93, 46, 18};
System.out.println(main.maxArrayValue(nums));
}
}
性能
