查找最大乘积子数组

Question

我们需要在一个数组（至少包含一个数字）中找到具有最大乘积的连续子数组，return 一个对应于最大可能乘积的整数。我发现这段代码可以解决同样的问题：

int maxProduct(const vector<int> &A)
{
    int n = A.size();
    vector<int> maxarray(n);
    vector<int> minarray(n);
    maxarray[0] = A[0];
    minarray[0] = A[0];
    int result = A[0];
    for(int i=1;i<n;i++){
        if(A[i]>0){
            maxarray[i] = max(A[i],maxarray[i-1]*A[i]);
            minarray[i] = min(A[i],minarray[i-1]*A[i]);
        }else{
            maxarray[i] = max(A[i],minarray[i-1]*A[i]);
            minarray[i] = min(A[i],maxarray[i-1]*A[i]);
        }
        result = max(result,maxarray[i]);
    }

    return result;
}

维护一个minarray需要什么？你能解释一下这些行吗：

if(A[i]>0){
            maxarray[i] = max(A[i],maxarray[i-1]*A[i]);
            minarray[i] = min(A[i],minarray[i-1]*A[i]);
        }else{
            maxarray[i] = max(A[i],minarray[i-1]*A[i]);
            minarray[i] = min(A[i],maxarray[i-1]*A[i]);
        }

为什么我们像上面的代码行那样更新 maxarray 和 minarray？

Answer 1

minarray的目的是处理负数。

{-1, 42, -2} 会 return 42 没有 minarray.

if (A[i]>0){
    maxarray[i] = max(A[i], maxarray[i-1]*A[i]);
    minarray[i] = min(A[i], minarray[i-1]*A[i]);
} else {
    maxarray[i] = max(A[i], minarray[i-1]*A[i]);
    minarray[i] = min(A[i], maxarray[i-1]*A[i]);
}

当A[i]为正时，prev*A[i]不改变符号。其他情况处理：当前一个值为 0

所以索引 i 之前的最大乘积是

A[i] 如果 maxarray[i-1] 为 0（或初始化为负数）
maxarray[i-1]*A[i] 否则。

std::max 简化条件。

同理，最小乘积（最大负数）为std::min(A[i], minarray[i-1] * A[i])。

当A[i]为负时，prev*A[i]做符号变换。所以最大值必须取之前的最小值

maxarray[i] = max(A[i], minarray[i-1] * A[i]);.

当A[i] == 0时，最大值和最小值都为0。（两个分支都可以）。

查找最大乘积子数组

Find maximum product subarray

c++

arrays

vector

dynamic-programming

sub-array