Version:1.0StartHTML:000000208EndHTML:000026213StartFragment:000013977EndFragment:000026133StartSelection:000013977EndSelection:000026117SourceURL:https://www.cnblogs.com/bakari/p/4007368.html
题目: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// 思路:用两个指针来指向字数组的头尾 2intmaxProduct(intA[],int n) 3{ 4assert(n >0); 5intsubArrayProduct = -32768; 6 7for(inti =0; i != n; ++ i) { 8intnTempProduct =1; 9for(intj = i; j != n; ++ j) {10if(j == i)11nTempProduct = A[i];12else13nTempProduct *= A[j];14if(nTempProduct >= subArrayProduct)15subArrayProduct = nTempProduct;16 }17 }18return subArrayProduct;19}
用动态规划的方法,就是要找到其转移方程式,也叫动态规划的递推式,动态规划的解法无非是维护两个变量,局部最优和全局最优,我们先来看Maximum SubArray的情况,如果遇到负数,相加之后的值肯定比原值小,但可能比当前值大,也可能小,所以,对于相加的情况,只要能够处理局部最大和全局最大之间的关系即可,对此,写出转移方程式如下:
local[i + 1] = Max(local[i] + A[i], A[i]);
global[i + 1] = Max(local[i + 1], global[i]);
对应代码如下:
1intmaxSubArray(intA[],int n) 2{ 3assert(n >0); 4if(n <=0) 5return0; 6intglobal= A[0]; 7intlocal = A[0]; 8 9for(inti =1; i != n; ++ i) {10local = MAX(A[i], local + A[i]);11global= MAX(local,global);12 }13returnglobal;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#defineMAX(x,y) ((x)>(y)?(x):(y)) 2#defineMIN(x,y) ((x)<(y)?(x):(y)) 3 4intmaxProduct1(intA[],int n) 5{ 6assert(n >0); 7if(n <=0) 8return0; 910if(n ==1)11returnA[0];12intmax_local = A[0];13intmin_local = A[0];1415intglobal= A[0];16for(inti =1; i != n; ++ i) {17intmax_copy = max_local;18max_local = MAX(MAX(A[i] * max_local, A[i]), A[i] * min_local);19min_local = MIN(MIN(A[i] * max_copy, A[i]), A[i] * min_local);20global= MAX(global, max_local);21 }22returnglobal;23}
总结:动态规划题最核心的步骤就是要写出其状态转移方程,但是如何写出正确的方程式,需要我们不断的实践并总结才能达到。
作者:Bakari
出处:https://www.cnblogs.com/bakari/p/4007368.html
本站使用「署名 4.0 国际」创作共享协议,转载请在文章明显位置注明作者及出处。
网友评论