c++ - 数组中相隔 8 个或更多位置的两个元素的最大乘积

Question

这是我目前遇到的问题和代码。

我有一个正数序列。序列的长度大于 8，负数(不是序列的一部分)是序列结束的标志。我需要编写一个程序(按时间和内存使用情况有效)找到由 8 个或更多位置分隔的 2 个元素的最大乘积。保证答案小于2000000000。

例如，对于 {1 2 3 4 5 6 7 8 9 10 -1}，答案将是 20。

我的代码:

#include <stdio.h>
#include <stdlib.h>

static long long int find_max(long int *v1, long int size) {
    const int d = 8;
    long int arr[8];
    long int maxi = 0;  
    long long int max_pr = 0;

    for (int i = 1; i < d + 1; i++) {
        arr[i % d] = v1[i - 1];
    }
    for (int j = d + 1; j < size + 1; j++) {
        if (arr[j % d] > maxi)
            maxi = arr[j % d];
        if (v1[j - 1] * maxi > max_pr)
            max_pr = v1[j - 1] * maxi;
        arr[j % d] = v1[j - 1];
    }
    return max_pr;
}

int main() {
    long int seq[100000];
    long int n = 0;

    while (n < 100000 && scanf("%ld", &seq[n]) == 1) {
        if (seq[n] < 0) {
            break;    //vector.push_back was too slow
        }
        n++;
    }

    long long int answer = find_max(seq, n);
    printf("%lld ", answer);

    return 0;
}

这是一道算法和数据结构公开课的作业题，与我的学位无关。我的代码在测试系统上失败。我已经尝试解决这个问题几天了，但无法理解我在这里做错了什么，因为它对我能想到的每个例子都运行良好。

如果有任何帮助，我将不胜感激。

Answer 1

这很容易在线性时间内完成，不需要任何额外的存储空间。想想哪些数字可能是可能的解决方案:它可能是第一个数字乘以第九个数字。它可能是前两个中最大的，乘以第十。它可以是前三个中最大的，乘以第十一个，依此类推。所以:

Set maxN = 0, maxProduct = 0, i = 0. 
As long as v1 [i + 8] ≥ 0:
    If v1 [i] > maxN then maxN = v1 [i]
    If v1 [i + 8] * maxN > maxProduct then maxProduct = v1 [i + 8] * maxN.
    Let i = i + 1.

就是这样。