首页 > 代码库 > LeetCode：Maximum Product Subarray
LeetCode：Maximum Product Subarray
题目：Maximum Product Subarray
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，现在是Product Subarray，不过思想是一致的。
当然不用动态规划，常规方法也是可以做的，但是时间复杂度过高（TimeOut），像下面这种形式：
1 // 思路：用两个指针来指向字数组的头尾 2 int maxProduct(int A[], int n) 3 { 4 assert(n > 0); 5 int subArrayProduct = -32768; 6 7 for (int i = 0; i != n; ++ i) { 8 int nTempProduct = 1; 9 for (int j = i; j != n; ++ j) {10 if (j == i)11 nTempProduct = A[i];12 else13 nTempProduct *= A[j];14 if (nTempProduct >= subArrayProduct)15 subArrayProduct = nTempProduct;16 }17 }18 return subArrayProduct;19 }
用动态规划的方法，就是要找到其转移方程式，也叫动态规划的递推式，动态规划的解法无非是维护两个变量，局部最优和全局最优，我们先来看Maximum SubArray的情况，如果遇到负数，相加之后的值肯定比原值小，但可能比当前值大，也可能小，所以，对于相加的情况，只要能够处理局部最大和全局最大之间的关系即可，对此，写出转移方程式如下：
local[i + 1] = Max(local[i] + A[i], A[i]);
global[i + 1] = Max(local[i + 1], global[i]);
对应代码如下：
1 int maxSubArray(int A[], int n) 2 { 3 assert(n > 0); 4 if (n <= 0) 5 return 0; 6 int global = A[0]; 7 int local = A[0]; 8 9 for(int i = 1; i != n; ++ i) {10 local = MAX(A[i], local + A[i]);11 global = MAX(local, global);12 }13 return global;14 }
而对于Product Subarray，要考虑到一种特殊情况，即负数和负数相乘：如果前面得到一个较小的负数，和后面一个较大的负数相乘，得到的反而是一个较大的数，如{2，-3，-7}，所以，我们在处理乘法的时候，除了需要维护一个局部最大值，同时还要维护一个局部最小值，由此，可以写出如下的转移方程式：
max_copy[i] = max_local[i]
max_local[i + 1] = Max(Max(max_local[i] * A[i], A[i]), min_local * A[i])
min_local[i + 1] = Min(Min(max_copy[i] * A[i], A[i]), min_local * A[i])
对应代码如下：
1 #define MAX(x,y) ((x)>(y)?(x):(y)) 2 #define MIN(x,y) ((x)<(y)?(x):(y)) 3 4 int maxProduct1(int A[], int n) 5 { 6 assert(n > 0); 7 if (n <= 0) 8 return 0; 9 10 if (n == 1)11 return A[0];12 int max_local = A[0];13 int min_local = A[0];14 15 int global = A[0];16 for (int i = 1; i != n; ++ i) {17 int max_copy = max_local;18 max_local = MAX(MAX(A[i] * max_local, A[i]), A[i] * min_local);19 min_local = MIN(MIN(A[i] * max_copy, A[i]), A[i] * min_local);20 global = MAX(global, max_local);21 }22 return global;23 }
总结：动态规划题最核心的步骤就是要写出其状态转移方程，但是如何写出正确的方程式，需要我们不断的实践并总结才能达到。
LeetCode：Maximum Product Subarray