首页 > 代码库 > Maximum Product Subarray动态规划思想

Maximum Product Subarray动态规划思想

该题即是昨天没有做出来的题目,想了很久,想出了一个普通的做法,提交发现超时了。思想是新建一个数组,保存每个元素与后面的元素相乘后得到的最大值,然后再在该数组中选出最大的值,返回。【笨死

发现行不通后决定还是求教度娘了。

果然大神无处不在,该题可运用动态规划思想解决。考虑到正负数相乘后会出现的各种结果,采取保存局部最小和局部最大值的方式。列出公式:

int a=localmin*A[i]

int b=localmax*A[i]

localmin = min(A[i],min(a,b))

localmax = max(A[i],max(a,b))

ans = max(ans,localmax)返回ans 即为所求。

 

需再多思考运用该方法。

 

Maximum Product Subarray动态规划思想