连续元素的数组中的最大产品 [英] The max product of consecutive elements in an array

问题描述

我在我的现场面试中遇到这个算法问题。因为我并没有被要求签署保密协议，在这里我张贴的答案。

I was asked this algorithm question during my onsite interview. Since I was not asked to sign NDA, I post it here for an answer.

鉴于真正的数字数组不包含0，发现产量最大的产品的连续元素。该算法应该以线性时间运行

Given an array of REAL numbers that does not contain 0, find the consecutive elements that yield max product. The algorithm should run in linear time

我已经考虑了以下方法： 使用两个数组。第一种是使用DP的想法来记录当前最大的绝对值的产品，第二个数组记录消极因素的数量满足为止。最终的结果应该是最大的最大绝对值和负号的数目为偶数。

I have considered the following approach: Use two arrays. First one is to use DP idea to record the current max absolute value product, the second array to record the number of negative elements met so far. The final result should be the largest max absolute value and the number of negative numbers be even.

我觉得我的方法将工作，但在编码表示将无法正常工作被打断。 请让我知道什么是在上面的方法失踪了。

I thought my method will work, but was interrupted during coding saying it will not work. Please let me know what is missing in the above approach.

推荐答案

该算法确实为O​​（n）。当迭代的数组，使用一个变量来存储迄今发现，一个变量来存储子阵列的最大值，在A [1]结束该最大值，和另一个变量来存储在一个端部最小值[I]来治疗负值。

The algorithm is indeed O(n). When iterating the array, use a variable to store the max value found so far, a variable to store the max value of subarray that ends at a[i], and another variable to store minimum value that ends at a[i] to treat negative values.

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;
}

有关需要在产品的至少两种元素的情况下，该算法可以被更新如下：

For the case of requiring at least two elements in the product, the algorithm can be updated as following:

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

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

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

这篇关于连续元素的数组中的最大产品的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！