Question

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

解法

方法一

class Solution:
  def maximumSumScore(self, nums: List[int]) -> int:
    s = [0] + list(accumulate(nums))
    return max(max(s[i + 1], s[-1] - s[i]) for i in range(len(nums)))

class Solution {
  public long maximumSumScore(int[] nums) {
    int n = nums.length;
    long[] s = new long[n + 1];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    long ans = Long.MIN_VALUE;
    for (int i = 0; i < n; ++i) {
      ans = Math.max(ans, Math.max(s[i + 1], s[n] - s[i]));
    }
    return ans;
  }
}

class Solution {
public:
  long long maximumSumScore(vector<int>& nums) {
    int n = nums.size();
    vector<long long> s(n + 1);
    for (int i = 0; i < n; ++i) s[i + 1] = s[i] + nums[i];
    long long ans = INT_MIN;
    for (int i = 0; i < n; ++i) ans = max(ans, max(s[i + 1], s[n] - s[i]));
    return ans;
  }
};

func maximumSumScore(nums []int) int64 {
  n := len(nums)
  s := make([]int64, n+1)
  for i, v := range nums {
    s[i+1] = s[i] + int64(v)
  }
  var ans int64 = math.MinInt64
  for i := 0; i < n; i++ {
    ans = max(ans, max(s[i+1], s[n]-s[i]))
  }
  return ans
}

function maximumSumScore(nums: number[]): number {
  const n = nums.length;
  let s = new Array(n + 1).fill(0);
  for (let i = 0; i < n; ++i) {
    s[i + 1] = s[i] + nums[i];
  }
  let ans = -Infinity;
  for (let i = 0; i < n; ++i) {
    ans = Math.max(ans, Math.max(s[i + 1], s[n] - s[i]));
  }
  return ans;
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumSumScore = function (nums) {
  const n = nums.length;
  let s = new Array(n + 1).fill(0);
  for (let i = 0; i < n; ++i) {
    s[i + 1] = s[i] + nums[i];
  }
  let ans = -Infinity;
  for (let i = 0; i < n; ++i) {
    ans = Math.max(ans, Math.max(s[i + 1], s[n] - s[i]));
  }
  return ans;
};