ZeroJudge 解題筆記：t164.連續成績

作者：王一哲
日期：2026年11月1日


ZeroJudge 題目連結：t164.連續成績

解題想法

每組測資第一列為一個整數 $n ~(1 \leq n \leq 2 \times 10^5)$，代表有 $n$ 場比賽；第二列有 $n$ 個整數 $a_i ~(-10^9 \leq a_i \leq 10^9)$，分別代表第 $i$ 場比賽的成績變化。找出一段非空連續區間，使這段區間的成績變化總和最大，並輸出該總和。

這題是連續區間最大和問題，很適合用滑動視窗 (sliding window) 解題。假設連續區間最大和為 $imax$，目前區間和為 $curr$，兩者預設值皆為第 0 場比賽的分數變化 $arr[0]$；視窗左端點 $left = 0$。用一個 for 迴圈更新視窗右端點 $right = 0$ 到 $n-1$，先更新 $curr += arr[right]$，再用一層 while 迴圈試著移除 $arr[left] \leq 0$ 的項目，使區間加總 $curr$ 盡量變大。如果跑完內層的 while 迴圈之後，$curr < arr[right]$，則改成以 $right$ 為新的區間起點，$curr = arr[right]$，$left = right$。for 迴圈最後才更新 $imax$。跑完 for 迴圈之後輸出 $imax$。

Python 程式碼

使用時間約為 11 ms，記憶體約為 9.6 MB，通過測試。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        # 讀取  n 場比賽的分數
        n = int(data[ptr])
        ptr += 1
        arr = tuple(map(int, data[ptr : ptr + n]))
        ptr += n
    
        # 用滑動視窗找連續區間加總最大值 imax
        # 目前的區間加總 curr，兩者皆預設為 arr[0]
        imax = curr = arr[0]
        left = 0
        for right in range(1, n):
            curr += arr[right]
            # 試著移除左端點小於、等於 0 的項目
            while left < right and arr[left] <= 0:
                curr -= arr[left]
                left += 1
            # 如果 curr 小於 arr[right]，以 right 為新的區間起點
            if curr <= arr[right]:
                curr = arr[right]
                left = right
            imax = max(imax, curr)
        result.append(f"{imax:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

使用時間約為 14 ms，記憶體約為 9.6 MB，通過測試。

while True:
    try:
        # 讀取  n 場比賽的分數
        n = int(input())
        arr = tuple(map(int, input().split()))
    except EOFError:
        break
    
    # 用滑動視窗找連續區間加總最大值 imax
    # 目前的區間加總 curr，兩者皆預設為 arr[0]
    imax = curr = arr[0]
    left = 0
    for right in range(1, n):
        curr += arr[right]
        # 試著移除左端點小於、等於 0 的項目
        while left < right and arr[left] <= 0:
            curr -= arr[left]
            left += 1
        # 如果 curr 小於 arr[right]，以 right 為新的區間起點
        if curr <= arr[right]:
            curr = arr[right]
            left = right
        imax = max(imax, curr)
    print(imax)

C++ 程式碼

使用時間約為 1 ms，記憶體約為 3.5 MB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    while(cin >> n) {
        // 讀取  n 場比賽的分數
        vector<long> arr (n);
        for(int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        
        // 用滑動視窗找連續區間加總最大值 imax
        // 目前的區間加總 curr，兩者皆預設為 arr[0]
        long imax = arr[0], curr = arr[0];
        int left = 0;  // 左端點
        for(int right = 1; right < n; right++) {
            curr += arr[right];
            // 試著移除左端點小於、等於 0 的項目
            while(left < right && arr[left] <= 0) {
                curr -= arr[left];
                left++;
            }
            // 如果 curr 小於 arr[right]，以 right 為新的區間起點
            if (curr <= arr[right]) {
                curr = arr[right];
                left = right;
            }
            imax = max(imax, curr);
        }
        cout << imax << "\n";
    }
    return 0;
}

C 語言程式碼

使用時間約為 1 ms，記憶體約為 3.2 MB，通過測試。

#include <stdio.h>
#define max(a, b) ((a) > (b) ? (a) : (b))

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        // 讀取  n 場比賽的分數
        long arr[200000];
        for(int i = 0; i < n; i++) {
            scanf("%ld", &arr[i]);
        }
        
        // 用滑動視窗找連續區間加總最大值 imax
        // 目前的區間加總 curr，兩者皆預設為 arr[0]
        long imax = arr[0], curr = arr[0];
        int left = 0;  // 左端點
        for(int right = 1; right < n; right++) {
            curr += arr[right];
            // 試著移除左端點小於、等於 0 的項目
            while(left < right && arr[left] <= 0) {
                curr -= arr[left];
                left++;
            }
            // 如果 curr 小於 arr[right]，以 right 為新的區間起點
            if (curr <= arr[right]) {
                curr = arr[right];
                left = right;
            }
            imax = max(imax, curr);
        }
        printf("%ld\n", imax);
    }
    return 0;
}