Medium

题目描述

给你一个长度为 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 <= 10^5
  • -10^9 <= nums[i] <= 10^9

解题思路

这道题要求我们找到数组的最优分割点，使得前缀和减去后缀最小值的得分最大。

核心思路：

根据题目提示，我们可以使用前缀和与后缀最小值数组来预处理。对于每个有效分割位置 i（0 <= i < n-1），计算 score(i) = prefixSum(i) - suffixMin(i)，然后找到最大得分。

具体步骤：

  1. 预计算前缀和数组：prefixSum[i] = nums[0] + nums[1] + … + nums[i]
  2. 预计算后缀最小值数组：suffixMin[i] = min(nums[i], nums[i+1], …, nums[n-1])
  3. 遍历所有有效分割位置：对于每个 i，计算 prefixSum[i] - suffixMin[i+1]，并维护最大值

优化思路：

我们也可以从右往左扫描一遍来计算后缀最小值，从左往右扫描一遍来计算前缀和，在同一次遍历中找到最大得分，这样可以优化空间复杂度。

这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)（如果不计算额外数组的话）。

代码实现

class Solution {
public:
    long long maximumScore(vector<int>& nums) {
        int n = nums.size();
        
        // 计算后缀最小值数组
        vector<int> suffixMin(n);
        suffixMin[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; i--) {
            suffixMin[i] = min(nums[i], suffixMin[i+1]);
        }
        
        long long maxScore = LLONG_MIN;
        long long prefixSum = 0;
        
        // 遍历所有有效分割位置
        for (int i = 0; i < n-1; i++) {
            prefixSum += nums[i];
            long long score = prefixSum - suffixMin[i+1];
            maxScore = max(maxScore, score);
        }
        
        return maxScore;
    }
};

class Solution:
    def maximumScore(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 计算后缀最小值数组
        suffix_min = [0] * n
        suffix_min[n-1] = nums[n-1]
        for i in range(n-2, -1, -1):
            suffix_min[i] = min(nums[i], suffix_min[i+1])
        
        max_score = float('-inf')
        prefix_sum = 0
        
        # 遍历所有有效分割位置
        for i in range(n-1):
            prefix_sum += nums[i]
            score = prefix_sum - suffix_min[i+1]
            max_score = max(max_score, score)
        
        return max_score

public class Solution {
    public long MaximumScore(int[] nums) {
        int n = nums.Length;
        
        // 计算后缀最小值数组
        int[] suffixMin = new int[n];
        suffixMin[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; i--) {
            suffixMin[i] = Math.Min(nums[i], suffixMin[i+1]);
        }
        
        long maxScore = long.MinValue;
        long prefixSum = 0;
        
        // 遍历所有有效分割位置
        for (int i = 0; i < n-1; i++) {
            prefixSum += nums[i];
            long score = prefixSum - suffixMin[i+1];
            maxScore = Math.Max(maxScore, score);
        }
        
        return maxScore;
    }
}

var maximumScore = function(nums) {
    const n = nums.length;
    
    // 计算后缀最小值数组
    const suffixMin = new Array(n);
    suffixMin[n-1] = nums[n-1];
    for (let i = n-2; i >= 0; i--) {
        suffixMin[i] = Math.min(nums[i], suffixMin[i+1]);
    }
    
    let maxScore = Number.NEGATIVE_INFINITY;
    let prefixSum = 0;
    
    // 遍历所有有效分割位置
    for (let i = 0; i < n-1; i++) {
        prefixSum += nums[i];
        const score = prefixSum - suffixMin[i+1];
        maxScore = Math.max(maxScore, score);
    }
    
    return maxScore;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要两次遍历数组，一次计算后缀最小值，一次计算前缀和并求最大得分
空间复杂度O(n)需要额外的后缀最小值数组存储空间