北京
2026-05-05：分割的最大得分。用go語言，給定一個(gè)長(zhǎng)度為 n 的整數(shù)數(shù)組 nums。需要在所有滿足 0 ≤ i < n?1 的位置中選擇一個(gè)切分點(diǎn) i，并計(jì)算該切分點(diǎn)的得分。
對(duì)每個(gè)切分點(diǎn) i：
? 先計(jì)算前綴和：prefixSum(i) = nums[0] + nums[1] + … + nums[i]
? 再計(jì)算后綴最小值：suffixMin(i) = 在 nums[i+1] 到 nums[n?1] 這段中的最小元素
? 分?jǐn)?shù)定義為：score(i) = prefixSum(i) ? suffixMin(i)
最后，要求返回所有這些切分點(diǎn) i 中 score(i) 的最大值。
2 <= nums.length <= 100000。
-1000000000 <= nums[i] <= 1000000000。
輸入： nums = [10,-1,3,-4,-5]。
輸出： 17。
解釋：
最優(yōu)的分割下標(biāo)是 i = 2，score(2) = prefixSum(2) - suffixMin(2) = (10 + (-1) + 3) - (-5) = 17。
題目來自力扣3788。
解題過程詳細(xì)拆解 一、明確題目核心規(guī)則
1.切分點(diǎn)范圍：數(shù)組長(zhǎng)度為5，切分點(diǎn)
i只能是0、1、2、3（滿足0 ≤ i < 4，保證前后都有元素）；2.單個(gè)切分點(diǎn)得分計(jì)算：
? 前綴和：
nums[0]到nums[i]的總和；? 后綴最小值：
nums[i+1]到數(shù)組末尾的最小數(shù)字；? 得分 = 前綴和 - 后綴最小值；
3.目標(biāo)：找出所有切分點(diǎn)中最大的得分。
二、整體解題步驟（分兩大階段） 第一階段：計(jì)算數(shù)組的總前綴和
首先把數(shù)組所有元素全部相加，得到一個(gè)總累加和，這個(gè)總和是后續(xù)計(jì)算所有切分點(diǎn)前綴和的基礎(chǔ)。
? 數(shù)組元素：10、-1、3、-4、-5
? 總累加和 = 10 + (-1) + 3 + (-4) + (-5) =3
我們從數(shù)組最后一個(gè)元素開始，倒著向前遍歷（保證前綴始終至少有1個(gè)元素），遍歷過程中做三件事：
1. 用總累加和減去當(dāng)前遍歷到的元素，得到當(dāng)前切分點(diǎn)的前綴和；
2. 持續(xù)更新后綴最小值（記錄當(dāng)前及右側(cè)所有元素的最小值）；
3. 計(jì)算當(dāng)前切分點(diǎn)的得分，記錄遍歷過程中的最大得分。
數(shù)組索引：0(10)、1(-1)、2(3)、3(-4)、4(-5)
總累加和初始值：3
后綴最小值初始值：極大值（比所有數(shù)字都大）
最大得分初始值：極小值（比所有可能得分都?。?/p>
第一步：遍歷索引4（元素-5）
1. 總累加和 減去 元素-5 → 3 - (-5) = 8（這是切分點(diǎn)i=3的前綴和：10-1+3-4=8）；
2. 更新后綴最小值：當(dāng)前后綴最小值（極大值）和-5比較，取更小的-5；
3. 計(jì)算得分：8 - (-5) = 13；
4. 記錄最大得分：當(dāng)前最大為13。
1. 總累加和 減去 元素-4 → 8 - (-4) = 12（這是切分點(diǎn)i=2的前綴和：10-1+3=12）；
2. 更新后綴最小值：當(dāng)前后綴最小值（-5）和-4比較，取更小的-5；
3. 計(jì)算得分：12 - (-5) = 17；
4. 記錄最大得分：17＞13，更新最大得分為17。
1. 總累加和 減去 元素3 → 12 - 3 = 9（這是切分點(diǎn)i=1的前綴和：10-1=9）；
2. 更新后綴最小值：當(dāng)前后綴最小值（-5）和3比較，取更小的-5；
3. 計(jì)算得分：9 - (-5) = 14；
4. 記錄最大得分：14＜17，最大得分保持17。
1. 總累加和 減去 元素-1 → 9 - (-1) = 10（這是切分點(diǎn)i=0的前綴和：10）；
2. 更新后綴最小值：當(dāng)前后綴最小值（-5）和-1比較，取更小的-5；
3. 計(jì)算得分：10 - (-5) = 15；
4. 記錄最大得分：15＜17，最大得分保持17。
遍歷完所有切分點(diǎn)后，最大得分是17，與題目輸出一致。
五、時(shí)間復(fù)雜度與額外空間復(fù)雜度 1. 時(shí)間復(fù)雜度
? 第一步計(jì)算總累加和：遍歷整個(gè)數(shù)組，時(shí)間復(fù)雜度為O(n)（n為數(shù)組長(zhǎng)度）；
? 第二步倒序遍歷計(jì)算得分：再次遍歷整個(gè)數(shù)組，時(shí)間復(fù)雜度為O(n)；
? 總時(shí)間復(fù)雜度：O(n)（線性時(shí)間，能高效處理n=10?的最大數(shù)據(jù)量）。
? 整個(gè)過程只使用了固定數(shù)量的變量（總累加和、后綴最小值、最大得分等）；
? 沒有創(chuàng)建任何與數(shù)組長(zhǎng)度n相關(guān)的額外數(shù)組、集合等數(shù)據(jù)結(jié)構(gòu)；
? 總額外空間復(fù)雜度：O(1)（常數(shù)級(jí)空間）。
1. 解題核心：倒序遍歷+動(dòng)態(tài)維護(hù)前綴和與后綴最小值，避免重復(fù)計(jì)算，保證高效性；
2. 時(shí)間復(fù)雜度：O(n)，適合處理十萬級(jí)長(zhǎng)度的數(shù)組；
3. 額外空間復(fù)雜度：O(1)，僅使用固定變量，無額外內(nèi)存開銷。
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-- { // 保證前綴至少有一個(gè)數(shù)
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): # 保證前綴至少有一個(gè)數(shù)
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--) { // 保證前綴至少有一個(gè)數(shù)
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;
}
我們相信人工智能為普通人提供了一種“增強(qiáng)工具”，并致力于分享全方位的AI知識(shí)。在這里，您可以找到最新的AI科普文章、工具評(píng)測(cè)、提升效率的秘籍以及行業(yè)洞察。 歡迎關(guān)注“福大大架構(gòu)師每日一題”，發(fā)消息可獲得面試資料，讓AI助力您的未來發(fā)展。
特別聲明：以上內(nèi)容(如有圖片或視頻亦包括在內(nèi))為自媒體平臺(tái)“網(wǎng)易號(hào)”用戶上傳并發(fā)布，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
