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. 1.切分點范圍：數組長度為5，切分點i只能是0、1、2、3（滿足0 ≤ i < 4，保證前后都有元素）；

2. 2.單個切分點得分計算：

• ? 前綴和：nums[0]到nums[i]的總和；

• ? 后綴最小值：nums[i+1]到數組末尾的最小數字；

• ? 得分 = 前綴和 - 后綴最小值；

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

二、整體解題步驟（分兩大階段） 第一階段：計算數組的總前綴和

首先把數組所有元素全部相加，得到一個總累加和，這個總和是后續計算所有切分點前綴和的基礎。

• ? 數組元素：10、-1、3、-4、-5

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

我們從數組最后一個元素開始，倒著向前遍歷（保證前綴始終至少有1個元素），遍歷過程中做三件事：

1. 1. 用總累加和減去當前遍歷到的元素，得到當前切分點的前綴和；

2. 2. 持續更新后綴最小值（記錄當前及右側所有元素的最小值）；

3. 3. 計算當前切分點的得分，記錄遍歷過程中的最大得分。

數組索引：0(10)、1(-1)、2(3)、3(-4)、4(-5)
總累加和初始值：3
后綴最小值初始值：極大值（比所有數字都大）
最大得分初始值：極小值（比所有可能得分都小）

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

1. 1. 總累加和 減去 元素-5 → 3 - (-5) = 8（這是切分點i=3的前綴和：10-1+3-4=8）；

2. 2. 更新后綴最小值：當前后綴最小值（極大值）和-5比較，取更小的-5；

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

4. 4. 記錄最大得分：當前最大為13。

1. 1. 總累加和 減去 元素-4 → 8 - (-4) = 12（這是切分點i=2的前綴和：10-1+3=12）；

2. 2. 更新后綴最小值：當前后綴最小值（-5）和-4比較，取更小的-5；

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

4. 4. 記錄最大得分：17＞13，更新最大得分為17。

1. 1. 總累加和 減去 元素3 → 12 - 3 = 9（這是切分點i=1的前綴和：10-1=9）；

2. 2. 更新后綴最小值：當前后綴最小值（-5）和3比較，取更小的-5；

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

4. 4. 記錄最大得分：14＜17，最大得分保持17。

1. 1. 總累加和 減去 元素-1 → 9 - (-1) = 10（這是切分點i=0的前綴和：10）；

2. 2. 更新后綴最小值：當前后綴最小值（-5）和-1比較，取更小的-5；

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

4. 4. 記錄最大得分：15＜17，最大得分保持17。

遍歷完所有切分點后，最大得分是17，與題目輸出一致。

五、時間復雜度與額外空間復雜度 1. 時間復雜度

• ? 第一步計算總累加和：遍歷整個數組，時間復雜度為O(n)（n為數組長度）；

• ? 第二步倒序遍歷計算得分：再次遍歷整個數組，時間復雜度為O(n)；

• ? 總時間復雜度：O(n)（線性時間，能高效處理n=10?的最大數據量）。

• ? 整個過程只使用了固定數量的變量（總累加和、后綴最小值、最大得分等）；

• ? 沒有創建任何與數組長度n相關的額外數組、集合等數據結構；

• ? 總額外空間復雜度：O(1)（常數級空間）。

1. 1. 解題核心：倒序遍歷+動態維護前綴和與后綴最小值，避免重復計算，保證高效性；

2. 2. 時間復雜度：O(n)，適合處理十萬級長度的數組；

3. 3. 額外空間復雜度：O(1)，僅使用固定變量，無額外內存開銷。

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助力您的未來發展。