2026-05-05：分割的最大得分。用go语言，给定一个长度为 n 的整数数组 nums。需要在所有满足 0 ≤ i < n−1 的位置中选择一...

2026-05-05：分割的最大得分。用go语言，给定一个长度为 n 的整数数组 nums。需要在所有满足 0 ≤ i < n−1 的位置中选择一个切分点 i，并计算该切分点的得分。

对每个切分点 i：

• 先计算前缀和：prefixSum(i) = nums[0] + nums[1] + … + nums[i]

• 再计算后缀最小值：suffixMin(i) = 在 nums[i+1] 到 nums[n−1] 这段中的最小元素

• 分数定义为：score(i) = prefixSum(i) − suffixMin(i)

最后，要求返回所有这些切分点 i 中 score(i) 的最大值。

2 <= nums.length <= 100000。

-1000000000 <= nums[i] <= 1000000000。

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

输出： 17。

解释：

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

题目来自力扣3788。

解题过程详细拆解 一、明确题目核心规则

1.切分点范围：数组长度为5，切分点i只能是0、1、2、3（满足0 ≤ i < 4，保证前后都有元素）；

2.单个切分点得分计算：

• 前缀和：nums[0]到nums[i]的总和；

• 后缀最小值：nums[i+1]到数组末尾的最小数字；

• 得分 = 前缀和 – 后缀最小值；

3.目标：找出所有切分点中最大的得分。

二、整体解题步骤（分两大阶段） 第一阶段：计算数组的总前缀和

首先把数组所有元素全部相加，得到一个总累加和，这个总和是后续计算所有切分点前缀和的基础。

• 数组元素：10、-1、3、-4、-5

• 总累加和 = 10 + (-1) + 3 + (-4) + (-5) =3

第二阶段：从后往前遍历，逐个计算所有切分点的得分

我们从数组最后一个元素开始，倒着向前遍历（保证前缀始终至少有1个元素），遍历过程中做三件事：

1. 用总累加和减去当前遍历到的元素，得到当前切分点的前缀和；

2. 持续更新后缀最小值（记录当前及右侧所有元素的最小值）；

3. 计算当前切分点的得分，记录遍历过程中的最大得分。

三、逐一遍历切分点的详细过程

数组索引：0(10)、1(-1)、2(3)、3(-4)、4(-5)
总累加和初始值：3
后缀最小值初始值：极大值（比所有数字都大）
最大得分初始值：极小值（比所有可能得分都小）

第一步：遍历索引4（元素-5）

1. 总累加和 减去 元素-5 → 3 – (-5) = 8（这是切分点i=3的前缀和：10-1+3-4=8）；

2. 更新后缀最小值：当前后缀最小值（极大值）和-5比较，取更小的-5；

3. 计算得分：8 – (-5) = 13；

4. 记录最大得分：当前最大为13。

第二步：遍历索引3（元素-4）

1. 总累加和 减去 元素-4 → 8 – (-4) = 12（这是切分点i=2的前缀和：10-1+3=12）；

2. 更新后缀最小值：当前后缀最小值（-5）和-4比较，取更小的-5；

3. 计算得分：12 – (-5) = 17；

4. 记录最大得分：17＞13，更新最大得分为17。

第三步：遍历索引2（元素3）

1. 总累加和 减去 元素3 → 12 – 3 = 9（这是切分点i=1的前缀和：10-1=9）；

2. 更新后缀最小值：当前后缀最小值（-5）和3比较，取更小的-5；

3. 计算得分：9 – (-5) = 14；

4. 记录最大得分：14＜17，最大得分保持17。

第四步：遍历索引1（元素-1）

1. 总累加和 减去 元素-1 → 9 – (-1) = 10（这是切分点i=0的前缀和：10）；

2. 更新后缀最小值：当前后缀最小值（-5）和-1比较，取更小的-5；

3. 计算得分：10 – (-5) = 15；

4. 记录最大得分：15＜17，最大得分保持17。

四、最终结果

遍历完所有切分点后，最大得分是17，与题目输出一致。

五、时间复杂度与额外空间复杂度 1. 时间复杂度

• 第一步计算总累加和：遍历整个数组，时间复杂度为O(n)（n为数组长度）；

• 第二步倒序遍历计算得分：再次遍历整个数组，时间复杂度为O(n)；

• 总时间复杂度：O(n)（线性时间，能高效处理n=10⁵的最大数据量）。

2. 额外空间复杂度

• 整个过程只使用了固定数量的变量（总累加和、后缀最小值、最大得分等）；

• 没有创建任何与数组长度n相关的额外数组、集合等数据结构；

• 总额外空间复杂度：O(1)（常数级空间）。

总结

1. 解题核心：倒序遍历+动态维护前缀和与后缀最小值，避免重复计算，保证高效性；

2. 时间复杂度：O(n)，适合处理十万级长度的数组；

3. 额外空间复杂度：O(1)，仅使用固定变量，无额外内存开销。

Go完整代码如下：

package main

 import (
    "fmt"
    "math"
)

 func maximumScore(nums []int) int64 {
    preSum := 0
    for _, x := range nums {
        preSum += x
    }

     ans := math.MinInt
    sufMin := math.MaxInt
    for i := len(nums) - 1; i > 0; i-- { // 保证前缀至少有一个数
        preSum -= nums[i] // 撤销
        sufMin = min(sufMin, nums[i])
        ans = max(ans, preSum-sufMin)
    }
    return int64(ans)
}

 func main() {
    nums := []int{10, -1, 3, -4, -5}
    result := maximumScore(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 from typing import List

 def maximumScore(nums: List[int]) -> int:
    pre_sum = sum(nums)
    ans = float('-inf')
    suf_min = float('inf')
    for i in range(len(nums) - 1, 0, -1):  # 保证前缀至少有一个数
        pre_sum -= nums[i]  # 撤销
        suf_min = min(suf_min, nums[i])
        ans = max(ans, pre_sum - suf_min)
    return int(ans)

 def main():
    nums = [10, -1, 3, -4, -5]
    result = maximumScore(nums)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  

  

  


 using namespace std;

 long long maximumScore(vector& nums) {
    int preSum = 0;
    for (int x : nums) {
        preSum += x;
    }

     int ans = INT_MIN;
    int sufMin = INT_MAX;

     for (int i = nums.size() - 1; i > 0; i--) { // 保证前缀至少有一个数
        preSum -= nums[i]; // 撤销
        sufMin = min(sufMin, nums[i]);
        ans = max(ans, preSum - sufMin);
    }

     return (long long)ans;
}

 int main() {
    vector nums = {10, -1, 3, -4, -5};
    long long result = maximumScore(nums);
    cout << result << endl;
    return 0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。