Skip to content

Latest commit

 

History

History
213 lines (170 loc) · 4.85 KB

README.md

File metadata and controls

213 lines (170 loc) · 4.85 KB
comments difficulty edit_url tags
true
中等
数组
前缀和

2219. 数组的最大总分 🔒

English Version

题目描述

给你一个下标从 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.length
  • 1 <= n <= 105
  • -105 <= nums[i] <= 105

解法

方法一：前缀和

我们可以使用两个变量 $l$ 和 $r$ 分别表示数组的前缀和和后缀和，初始时 $l = 0$, $r = \sum_{i=0}^{n-1} \textit{nums}[i]$。

接下来，我们遍历数组 $\textit{nums}$，对于每个元素 $x$，我们将 $l$ 增加 $x$，并更新答案 $\textit{ans} = \max(\textit{ans}, l, r)$，然后将 $r$ 减少 $x$。

遍历结束后，返回答案 $\textit{ans}$ 即可。

时间复杂度 $O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$。

Python3

class Solution:
    def maximumSumScore(self, nums: List[int]) -> int:
        l, r = 0, sum(nums)
        ans = -inf
        for x in nums:
            l += x
            ans = max(ans, l, r)
            r -= x
        return ans

Java

class Solution {
    public long maximumSumScore(int[] nums) {
        long l = 0, r = 0;
        for (int x : nums) {
            r += x;
        }
        long ans = Long.MIN_VALUE;
        for (int x : nums) {
            l += x;
            ans = Math.max(ans, Math.max(l, r));
            r -= x;
        }
        return ans;
    }
}

C++

class Solution {
public:
    long long maximumSumScore(vector<int>& nums) {
        long long l = 0, r = accumulate(nums.begin(), nums.end(), 0LL);
        long long ans = -1e18;
        for (int x : nums) {
            l += x;
            ans = max({ans, l, r});
            r -= x;
        }
        return ans;
    }
};

Go

func maximumSumScore(nums []int) int64 {
	l, r := 0, 0
	for _, x := range nums {
		r += x
	}
	ans := math.MinInt64
	for _, x := range nums {
		l += x
		ans = max(ans, max(l, r))
		r -= x
	}
	return int64(ans)
}

TypeScript

function maximumSumScore(nums: number[]): number {
    let l = 0;
    let r = nums.reduce((a, b) => a + b, 0);
    let ans = -Infinity;
    for (const x of nums) {
        l += x;
        ans = Math.max(ans, l, r);
        r -= x;
    }
    return ans;
}

Rust

impl Solution {
    pub fn maximum_sum_score(nums: Vec<i32>) -> i64 {
        let mut l = 0;
        let mut r: i64 = nums.iter().map(|&x| x as i64).sum();
        let mut ans = std::i64::MIN;
        for &x in &nums {
            l += x as i64;
            ans = ans.max(l).max(r);
            r -= x as i64;
        }
        ans
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumSumScore = function (nums) {
    let l = 0;
    let r = nums.reduce((a, b) => a + b, 0);
    let ans = -Infinity;
    for (const x of nums) {
        l += x;
        ans = Math.max(ans, l, r);
        r -= x;
    }
    return ans;
};