首页 > 代码库 > [C++]LeetCode: 96 Maximum Product Subarray(动态规划)

[C++]LeetCode: 96 Maximum Product Subarray(动态规划)

2024-11-05 00:07:39   203人阅读

题目：

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

思路：

这道题和Maximum Subarray解法类似，维护两个变量来动态规划，一个局部最优，一个全局最优。第i步的局部最优，表示的是必须包含A[i-1](当前元素)的局部最优解，全局最优是到当前元素为止的最优值。讨论动态规划的递推式，假设我们已知第i步的global[i]和local[i]，第i+1步的表达式：local[i+1] = max(A[i], local[i]+A[i]), 局部最优必须包含当前元素，所以是上一步的局部最优（包含上一个数组元素）local[i]+当前元素A[i](local[i] 包含第i个元素，A[i]是第i+1个元素，这样计算是符合题设的)，如果local[i]是负值，则加上它无法保证当前局部最优，所以取A[i]. global[i+1] = max(global[i], local[i+1]). 有了当前一步的局部最优，那全局最优就是当前的局部最优或者还是原来的全局最优（全局最优始终维护着所有解的最优解，包含所有情况，如果最优解不包含当前元素，那么前面会被维护在全局最优解里，如果包含当前元素，此时的解就是局部最优）

根据以上的分析，我们可以得到 Maximum Subarray的AC Code:

class Solution {
public:
    int maxSubArray(int A[], int n) {
        if(n == 0) return 0;
        int local = A[0];
        int global = A[0];
        
        for(int i = 1; i < n; i++)
        {
            local = max(local + A[i], A[i]);
            global = max(global, local);
        }
        
        return global;
    }
};

现在我们来分析下这道题，这道题模型和思路都和上道题很类似 ，还是用一维动态规划中的“局部最优和全局最优法“。不同的是，我们需要考虑乘法的特性，只是维护一个局部最优不足以得到后面的全局最优。因为乘法和加法不同，累加结果只要是正就一定递增，乘法可能上一个结果为负值，后面再出现（不需要相邻）另外一个负数相乘就会得到更大的乘积（负负为正）。所以我们这里需要维护三个变量，局部最大，局部最小，全局最大。局部最大的定义，维护从0~k，包含当前元素的局部最大（一定包含k）。

f(k) = Largest product subarray, from index 0 up to k.

接下来，我们来看下递推公式：假设我们得到了第i 步的当前的局部最大maxlocal[i]， 局部最小minlocal[i], 全局最大global[i]. 则第i+1步的局部最大maxlocal[i+1] = max( A[i], maxlocal[i] * A[i],  minlocal[i] * A[i])， minlocal[i+1] = min(A[i], maxlocal[i] *A[i], minlocal[i]*A[i]), global[i+1] = max(maxlocal, global); 得到了递推公式，接下来我们就可以敲代码了。这道题是个不错的面试题目，上道题比较常见，这道题模型相似，又有新的考点。还能考察动态规划，需要我们面对具体的问题，仔细分析和思考，彻底理解了方法，才能做到举一而反三。

Attention：

1. 注意此题中是乘法，需要考虑乘法的特性，需要多维护一个变量minlocal.

2. 注意我们动态规划时，求解minlocal[i+1]时使用的时上一个maxlocal[i], 所以需要在局部最优更新前，先保存maxlocal[i]

int maxcopy = maxlocal;
            maxlocal = max(max(maxlocal*A[i], A[i]), minlocal*A[i]);
            minlocal = min(min(maxcopy*A[i], A[i]), minlocal*A[i]);
            global = max(maxlocal, global);

3. 特殊情况，不能忘记，假如数组没有元素，返回0.

4. max 和min函数的参数是两个值，只能两个值作比较，所以要两次调用函数。

maxlocal = max(max(maxlocal*A[i], A[i]), minlocal*A[i]);
minlocal = min(min(maxcopy*A[i], A[i]), minlocal*A[i]);

复杂度：O(n)

AC Code:

class Solution {
public:
    int maxProduct(int A[], int n) {
        if(n == 0) return 0;
        if(n == 1) return A[0];
        
        int maxlocal = A[0];
        int minlocal = A[0];
        int global = A[0];
        
        for(int i = 1; i < n; i++)
        {
            int maxcopy = maxlocal;
            maxlocal = max(max(maxlocal*A[i], A[i]), minlocal*A[i]);
            minlocal = min(min(maxcopy*A[i], A[i]), minlocal*A[i]);
            global = max(maxlocal, global);
        }
        
        return global;
    }
};



[C++]LeetCode: 96 Maximum Product Subarray(动态规划)


联系
我们