3788. 分割的最大得分

English Version

题目描述

给你一个长度为 n 的整数数组 nums。

请你选出一个下标 i 以分割数组，该下标满足 0 <= i < n - 1。

对于选择的分割下标 i：

• 令 prefixSum(i) 表示数组前缀的和，即 nums[0] + nums[1] + ... + nums[i]。
• 令 suffixMin(i) 表示数组后缀的最小值，即 nums[i + 1], nums[i + 2], ..., nums[n - 1] 中的最小值。

在下标 i 的 分割得分 定义为：

score(i) = prefixSum(i) - suffixMin(i)

返回所有有效分割下标中 最大 的分割得分。

 

示例 1：

示例 2：

示例 3：

 

提示：

• 2 <= nums.length <= 105
• -109​​​​​​​ <= nums[i] <= 109

解法

方法一：前缀和 + 枚举

我们首先定义一个长度为 $n$ 的数组 $\textit{suf}$，其中 $\textit{suf}[i]$ 表示数组 $\textit{nums}$ 从下标 $i$ 到下标 $n - 1$ 的最小值。我们可以从后向前遍历数组 $\textit{nums}$ 来计算数组 $\textit{suf}$。

接下来，我们定义一个变量 $\textit{pre}$ 来表示数组 $\textit{nums}$ 的前缀和。我们遍历数组 $\textit{nums}$ 的前 $n - 1$ 个元素，对于每个下标 $i$，我们将 $\textit{nums}[i]$ 加入到 $\textit{pre}$ 中，并计算分割得分 $\textit{score}(i) = \textit{pre} - \textit{suf}[i + 1]$。我们使用一个变量 $\textit{ans}$ 来维护所有分割得分的最大值。

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

Python3

class Solution:
    def maximumScore(self, nums: List[int]) -> int:
        n = len(nums)
        suf = [nums[-1]] * n
        for i in range(n - 2, -1, -1):
            suf[i] = min(nums[i], suf[i + 1])
        ans = -inf
        pre = 0
        for i in range(n - 1):
            pre += nums[i]
            ans = max(ans, pre - suf[i + 1])
        return ans

Java

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

C++

class Solution {
public:
    long long maximumScore(vector<int>& nums) {
        int n = nums.size();
        vector<long long> suf(n);
        suf[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            suf[i] = min((long long) nums[i], suf[i + 1]);
        }
        long long ans = LLONG_MIN;
        long long pre = 0;
        for (int i = 0; i < n - 1; ++i) {
            pre += nums[i];
            ans = max(ans, pre - suf[i + 1]);
        }
        return ans;
    }
};

Go

func maximumScore(nums []int) int64 {
	n := len(nums)
	suf := make([]int64, n)
	suf[n-1] = int64(nums[n-1])
	for i := n - 2; i >= 0; i-- {
		suf[i] = min(int64(nums[i]), suf[i+1])
	}
	var pre int64 = 0
	var ans int64 = math.MinInt64
	for i := 0; i < n-1; i++ {
		pre += int64(nums[i])
		ans = max(ans, pre-suf[i+1])
	}
	return ans
}

TypeScript

function maximumScore(nums: number[]): number {
    const n = nums.length;
    const suf: number[] = new Array(n);
    suf[n - 1] = nums[n - 1];
    for (let i = n - 2; i >= 0; --i) {
        suf[i] = Math.min(nums[i], suf[i + 1]);
    }
    let ans = Number.NEGATIVE_INFINITY;
    let pre = 0;
    for (let i = 0; i < n - 1; ++i) {
        pre += nums[i];
        ans = Math.max(ans, pre - suf[i + 1]);
    }
    return ans;
}