跳转至

3788. 分割的最大得分

题目描述

给你一个长度为 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：

输入： nums = [10,-1,3,-4,-5]

输出： 17

解释：

最优的分割下标是 i = 2，score(2) = prefixSum(2) - suffixMin(2) = (10 + (-1) + 3) - (-5) = 17。

示例 2：

输入： nums = [-7,-5,3]

输出： -2

解释：

最优的分割下标是 i = 0，score(0) = prefixSum(0) - suffixMin(0) = (-7) - (-5) = -2。

示例 3：

输入： nums = [1,1]

输出： 0

解释：

唯一有效分割下标是 i = 0，score(0) = prefixSum(0) - suffixMin(0) = 1 - 1 = 0。

 

提示：

  • 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}\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
}

评论