如何进一步优化Project-Euler #8的最大相邻13位数字乘积算法？

我已经解决了Project-Euler #8的问题，但想寻求更高效的算法优化。

问题描述 #

给定数字文本数组DATA，找出其中乘积最大的13个相邻数字。

已实现方案 #

• 核心逻辑：遍历每个数字，计算连续13位的乘积，保留最大值。
• 第一轮优化-分块：跳过含0的片段，仅保留长度≥13的非0连续数字块（chunk）。

当前问题 #

分块后仍有约263个chunk，希望筛选掉"权重较低"的chunk以进一步优化。

现有实现代码 #

//Method: (DATA, window_size) ---> largest product of adjacent digits  
data func(char textnum[], int n)
{
    //Sub-method: DATA[char] ---> DATA[int]
    int bignum[1000];

    for(int i = 0; i < 1000; i++ )
    {
        bignum[i] = int( textnum[i] ) - 48;
    }

    //Chunking: In between zeros, all the (adjacent digits) < n are dropped
    //int chunk[] : holds the index to an appropriate "chunk"
    int cnt = 0, s = 0;

    std::vector<int> chunks;

    for ( int i = 0; i < 1000; i++ )
    {
        if( bignum[i] )
            cnt++;
        else cnt = 0;
        if( cnt >= n )
        {
            chunks.push_back((i + 1) - n); 
        }
    }

    //Main Logic: 
    data p = 1, x = 1;
    for ( int i = 0; i < chunks.size(); i++)    //Loop: (processing through chunks in DATA)
    {
        for ( int j = 0; j < n; j++ )           //Loop: (processing till the window_size)
        {
            p *= bignum[chunks.at(i) + j];      //Product of n adjacent digits
        }
        if ( p > x )                            //Largest 
            x = p;
        p = 1;
    }

    return x;
}

1. 滑动窗口替代全窗口重算 #

当前代码对每个chunk的起始位置都重新计算13个数字的乘积，会重复计算大量重叠部分。改用滑动窗口可将时间复杂度从O(M*N)降至O(M)（M为chunk总长度，N为窗口大小13）：

• 先计算第一个窗口的乘积；
• 后续窗口乘积 = 前一个窗口乘积 / 移出窗口的数字 * 移入窗口的数字；
• 由于已过滤含0的chunk，无需担心除以0的问题。

示例代码片段：

// 处理单个非0chunk（start为chunk起始索引，length为chunk长度）
data current_product = 1;
// 计算第一个窗口
for(int j = start; j < start + n; j++){
    current_product *= bignum[j];
}
data max_product = current_product;
// 滑动窗口遍历剩余位置
for(int j = start + n; j < start + length; j++){
    current_product = current_product / bignum[j - n] * bignum[j];
    if(current_product > max_product){
        max_product = current_product;
    }
}
// 更新全局最大值
if(max_product > x) x = max_product;

2. 预筛选低权重chunk #

提前排除不可能产生最大乘积的chunk，可从以下角度入手：

• 统计高值数字占比：乘积最大的窗口大概率包含更多9、8、7这类大数字。给每个chunk统计≥7的数字数量，直接跳过占比极低的chunk；
• 计算理论最大乘积：若某个chunk中最大的13个数字的乘积小于当前全局最大值，直接跳过该chunk。遍历chunk时记录前13大的数字，计算它们的乘积，若小于当前x则无需处理整个chunk；
• 合并重叠起始点：当前chunks数组会加入大量重叠的起始索引（比如长度100的chunk会加入88个起始点），改为收集每个完整chunk的起始、结束索引，而非单个起始位置，可大幅减少chunk数量。

修改后的chunk收集逻辑示例：

std::vector<std::pair<int, int>> chunks; // 存储每个chunk的(起始索引, 结束索引)
int start = -1;
for(int i = 0; i < 1000; i++){
    if(bignum[i] != 0){
        if(start == -1) start = i;
    } else {
        if(start != -1 && (i - start) >= n){
            chunks.emplace_back(start, i-1);
        }
        start = -1;
    }
}
// 处理最后一个未被截断的chunk
if(start != -1 && (1000 - start) >= n){
    chunks.emplace_back(start, 999);
}

3. 避免大数溢出与计算优化 #

13个9的乘积为2541865828329，已超出32位整数范围，可做如下优化：

• 改用64位整数（如long long）或大整数类型；
• 用对数转换比较大小：乘积的对数等于各数字对数的和，通过计算窗口的对数和来比较大小，避免直接计算大数乘积，最后再验证最大对数和对应的实际乘积。

内容的提问来源于stack exchange，提问作者user13793398