ZeroJudge 解題筆記：a540. 10684 - The jackpot

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


ZeroJudge 題目連結：a540. 10684 - The jackpot

解題想法

這題考 Kadane's Algorithm，詳細的說明可以參考這篇 Maximum Subarray Sum - Kadane's Algorithm。

Python 程式碼

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

import sys

result = []
lines = sys.stdin.readlines()
idx = 0
while idx < len(lines):
    n = int(lines[idx])
    idx += 1
    if n == 0: break
    nums = list(map(int, lines[idx].split()))
    idx += 1
    curr = imax = nums[0]
    for num in nums[1:]:
        # 如果用前面累積的值加上 num 較大，取這個值，反之取 num 重新開始
        curr = max(num, curr + num)
        imax = max(imax, curr)
    if imax > 0:
        result.append(f"The maximum winning streak is {imax:d}.\n")
    else:
        result.append("Losing streak.\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 2 ms，記憶體約為 72 kB，通過測試。

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int N;  // 數列長度
    while(scanf("%d", &N) != EOF) {
        if (N == 0) continue;
        int arr[N];  // 數列
        for(int i=0; i<N; i++) scanf("%d", &arr[i]);
        int curr = arr[0], imax = arr[0];
        for(int i=1; i<N; i++) {
            curr = max(curr+arr[i], arr[i]);
            imax = max(imax, curr);
        }
        if (imax <=0) puts("Losing streak.");
        else printf("The maximum winning streak is %d.\n", imax);
    }
    return 0;
}