首页 > 代码库 > 【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.
解题思路：乘法与加法最大差别在于，当前元素的符号具有全局性的作用。
如果当前元素为负，那么连乘到上个元素的最大乘积，再乘以当前元素，就变成负数，甚至可能成为最小乘积。
同样，连乘到上个元素的最小乘积如为负，再乘以当前元素，就变成正数，甚至可能成为最大乘积。
因此使用动态规划的方法：
记maxPro_last/minPro_last为连乘到上个元素的最大/小乘积
记maxPro_cur/minPro_cur为连乘到当前元素的最大/小乘积
记maxPro_all/minPro_all为截至（可不包括）当前元素的最大/小乘积
简化起见可以忽略对当前元素正负性分析，把当前元素与maxPro_last/minPro_last的乘积都作为产生maxPro_cur/minPro_cur的情况
class Solution {public: int maxProduct(int A[], int n) { if(n == 0) return 0; //到当前元素为止，最大/小乘积 int maxPro_all = A[0]; //以前一个元素为连乘末元素的最大/小乘积 int maxPro_last = A[0]; int minPro_last = A[0]; //以当前元素为连乘末元素的最大/小乘积 int maxPro_cur = A[0]; int minPro_cur = A[0]; for(int i = 1; i < n; i ++) { maxPro_cur = max(A[i], max(maxPro_last*A[i], minPro_last*A[i])); minPro_cur = min(A[i], min(maxPro_last*A[i], minPro_last*A[i])); maxPro_all = max(maxPro_cur, maxPro_all); maxPro_last = maxPro_cur; minPro_last = minPro_cur; } return maxPro_all; }};
【LeetCode】Maximum Product Subarray
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。