Project Euler 第 8 題：1000 位數字中連續 5 位最大乘積

問題描述

給定一個 1000 位數字字串，找出連續 5 位數字乘積的最大值。

簡單暴力解法

#include <stdio.h>
#include <string.h>

int main() {
    const char *num =
        "73167176531330624919225119674426574742355349194934"
        "96983520312774506326239578318016984801869478851843"
        "... (共 1000 位) ...";

    long long maxProd = 0;
    int len = strlen(num);
    for (int i = 0; i <= len - 5; i++) {
        long long p = 1;
        for (int k = 0; k < 5; k++)
            p *= (num[i+k] - '0');
        if (p > maxProd) maxProd = p;
    }
    printf("最大乘積: %lld\n", maxProd);  // 40824
    return 0;
}

優化：滑動窗口避免重複乘除

若窗口內無 0，可用除法移除舊數字、乘法加入新數字。但 5 位窗口極小，暴力 O(N) 已極快（1000×5=5000 次乘法），優化意義不大。

原始碼問題分析

• 陣列初始化語法錯誤：str[]={ ... } 缺少引號與逗號分隔。
• 迴圈條件寫法錯誤：i<;、i=i+ 等不完整片段。
• 嘗試跳過含 0 窗口的邏輯不完整（i=i+4 等）。
• 未使用 long long，5 位最大乘積 9⁵=59049 尚可放入 int，但習慣用長整型。

進階：任意窗口大小 K

long long maxProduct(const char *s, int k) {
    long long maxP = 0, curP = 1;
    int zeroCount = 0, len = strlen(s);
    for (int i=0; i= k) {
            int old = s[i-k] - '0';
            if (old == 0) zeroCount--;
            else curP /= old;
        }
        if (i >= k-1 && zeroCount == 0 && curP > maxP)
            maxP = curP;
    }
    return maxP;
}

執行結果

最大乘積: 40824  (對應數字 9,9,8,9,9 或類似組合)

Project Euler 8 題是滑動窗口與字串數字處理的入門練習，關鍵在正確轉換字元為數值、選擇適當資料型別、處理邊界條件。