class Solution {
public:
long long maximumSumScore(vector<int>& nums) {
}
};
2219. 数组的最大总分
给你一个下标从 0 开始的整数数组 nums ，数组长度为 n 。
nums 在下标 i （0 <= i < n）处的 总分 等于下面两个分数中的 最大值 ：
nums 前 i + 1 个元素的总和nums 后 n - i 个元素的总和返回数组 nums 在任一下标处能取得的 最大总分 。
示例 1：
输入：nums = [4,3,-2,5] 输出：10 解释： 下标 0 处的最大总分是 max(4, 4 + 3 + -2 + 5) = max(4, 10) = 10 。 下标 1 处的最大总分是 max(4 + 3, 3 + -2 + 5) = max(7, 6) = 7 。 下标 2 处的最大总分是 max(4 + 3 + -2, -2 + 5) = max(5, 3) = 5 。 下标 3 处的最大总分是 max(4 + 3 + -2 + 5, 5) = max(10, 5) = 10 。 nums 可取得的最大总分是 10 。
示例 2：
输入：nums = [-3,-5] 输出：-3 解释： 下标 0 处的最大总分是 max(-3, -3 + -5) = max(-3, -8) = -3 。 下标 1 处的最大总分是 max(-3 + -5, -5) = max(-8, -5) = -5 。 nums 可取得的最大总分是 -3 。
提示：
n == nums.length1 <= n <= 105-105 <= nums[i] <= 105原站题解
golang 解法, 执行用时: 36 ms, 内存消耗: 8.1 MB, 提交时间: 2023-10-22 08:44:03
func maximumSumScore(nums []int) int64 {
sum:= 0
for i := 0; i < len(nums); i++ {
sum+=nums[i]
}
ans:=sum
cur:=0
for i := 0; i < len(nums); i++ {
cur+= nums[i]
if cur > ans{
ans = cur
}
if sum > ans{
ans = sum
}
sum-=nums[i]
}
return int64(ans)
}
java 解法, 执行用时: 3 ms, 内存消耗: 55.3 MB, 提交时间: 2023-10-22 08:43:36
class Solution {
public long maximumSumScore(int[] nums) {
long[] list = new long[nums.length + 1];
long sum = 0;
long maxSum = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
list[i + 1] = sum;
maxSum = Math.max(maxSum, sum);
}
for (int i = 1; i < list.length - 1; i++) {
maxSum = Math.max(maxSum, list[list.length - 1] - list[i]);
}
return maxSum;
}
}
python3 解法, 执行用时: 88 ms, 内存消耗: 30.1 MB, 提交时间: 2023-10-22 08:43:19
class Solution:
# 前缀和
def maximumSumScore(self, nums: List[int]) -> int:
presum, n = [0] + list(accumulate(nums)), len(nums)
return max(max(presum[i + 1], presum[n] - presum[i]) for i in range(n))
# 暴力
def maximumSumScore2(self, nums: List[int]) -> int:
p, s, ans = 0, sum(nums), -inf
for num in nums:
ans = max(ans, max(p + num, s - p))
p += num
return ans
cpp 解法, 执行用时: 60 ms, 内存消耗: 38.9 MB, 提交时间: 2023-10-22 08:42:18
class Solution {
public:
long long maximumSumScore(vector<int>& nums) {
if (nums.size() == 0) return nums[0];
int n = nums.size();
long long cursum = 0, ans = INT_MIN;
for (int i = 0; i < n; ++i) {
cursum += nums[i];
ans = max(ans, cursum);
}
cursum = 0;
for (int i = n - 1; i >= 0; --i) {
cursum += nums[i];
ans = max(ans, cursum);
}
return ans;
}
};