class Solution {
public:
long long maxArrayValue(vector<int>& nums) {
}
};
6915. 合并后数组中的最大元素
给你一个下标从 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 <= 1051 <= nums[i] <= 106原站题解
php 解法, 执行用时: 259 ms, 内存消耗: 27.2 MB, 提交时间: 2024-03-14 10:07:39
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function maxArrayValue($nums) {
$n = count($nums) - 1;
while ($n >= 0) {
while ($n > 0 && $nums[$n - 1] <= $nums[$n]) {
$nums[$n - 1] += $nums[$n];
$n--;
}
$n--;
}
return $nums[0];
}
}
javascript 解法, 执行用时: 112 ms, 内存消耗: 52.3 MB, 提交时间: 2023-07-24 10:01:43
/**
* @param {number[]} nums
* @return {number}
*/
var maxArrayValue = function(nums) {
let max = nums.pop();
while (nums.length) {
const pop = nums.pop();
max = max >= pop ? max + pop : pop;
}
return max;
};
python3 解法, 执行用时: 204 ms, 内存消耗: 27 MB, 提交时间: 2023-07-24 10:00:40
class Solution:
def maxArrayValue(self, nums: List[int]) -> int:
for i in range(len(nums) - 2, -1, -1):
if nums[i] <= nums[i + 1]:
nums[i + 1] += nums[i]
nums.pop(i)
return max(nums)
python3 解法, 执行用时: 180 ms, 内存消耗: 31.8 MB, 提交时间: 2023-07-24 10:00:25
class Solution:
def maxArrayValue(self, nums: List[int]) -> int:
n = len(nums) - 1
while n >= 0:
while n > 0 and nums[n - 1] <= nums[n]:
nums[n - 1] += nums[n]
n -= 1
n -= 1
return nums[0]
golang 解法, 执行用时: 136 ms, 内存消耗: 9.1 MB, 提交时间: 2023-07-24 09:58:09
func maxArrayValue(nums []int) int64 {
n := len(nums)
ans, res := nums[n-1], nums[n-1]
for i := n-2; i >= 0; i-- {
if nums[i] <= res {
res += nums[i]
} else {
res = nums[i]
}
if res > ans {
ans = res
}
}
return int64(ans)
}
cpp 解法, 执行用时: 116 ms, 内存消耗: 102.9 MB, 提交时间: 2023-07-24 09:55:37
class Solution {
public:
long long maxArrayValue(vector<int>& nums) {
int n = nums.size();
long long ans = nums[n - 1];
long long sum = nums[n - 1];
/* 从后往前模拟即可 */
for (int i = n - 2; i >= 0; i--) {
if (nums[i] <= sum) {
sum += nums[i];
} else {
sum = nums[i];
}
ans = max(ans, sum);
}
return ans;
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 56.8 MB, 提交时间: 2023-07-24 09:55:16
/**
* 从后往前遍历数组，设置一个迭代变量res，如果res>=nums[i],
* 则迭代变量res+=nums[i]，否则res=nums[i]，在遍历过程中更新ans
**/
class Solution {
public long maxArrayValue(int[] nums) {
int len = nums.length;
long max = nums[len -1];
for (int i = len - 2; i >= 0; i--) max = (max >= nums[i] ? max + nums[i] : nums[i]);
return max;
}
}
java 解法, 执行用时: 1 ms, 内存消耗: 56.6 MB, 提交时间: 2023-07-24 09:53:58
/**
* 从后往前遍历数组，设置一个迭代变量res，如果res>=nums[i],
* 则迭代变量res+=nums[i]，否则res=nums[i]，在遍历过程中更新ans
**/
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;
}
}