algorithm - 数组中连续元素的最大乘积

Question

我在现场面试时被问到这个算法问题。由于没有要求我签署 NDA，因此我将其张贴在这里以寻求答案。

给定一个不包含 0 的 REAL 数组，找到产生最大乘积的连续元素。该算法应该在线性时间内运行

我考虑过以下方法:使用两个数组。第一个是用DP思想记录当前最大绝对值乘积，第二个数组记录到目前为止遇到的负元素个数。最后的结果应该是最大的max绝对值，负数的个数必须是偶数。

我认为我的方法会奏效，但在编码过程中被打断说它不会奏效。请让我知道上述方法中缺少什么。

Answer 1

算法确实是O(n)。迭代数组时，用一个变量存放目前找到的最大值，一个变量存放以a[i]结尾的子数组的最大值，另一个变量存放以a[i]结尾的最小值待处理负值。

float find_maximum(float arr[], int n) {
    if (n <= 0) return NAN;

    float max_at = arr[0];  // Maximum value that ends at arr[i]
    float min_at = arr[0];  // Minimum value that ends at arr[i]
    float max_value = max_at;

    for (int i = 1; i < n; i++) {
        float prev_max_at = max_at, prev_min_at = min_at;
        max_at = max(arr[i], arr[i] * prev_min_at, arr[i] * prev_max_at);
        min_at = min(arr[i], arr[i] * prev_min_at, arr[i] * prev_max_at);
        max_value = max(max_value, max_at);
    }
    return max_value;
}