首页 > 代码库 > 1014------算法笔记----------Maximum Product Subarray 最大乘积子数组
1014------算法笔记----------Maximum Product Subarray 最大乘积子数组
1.题目
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.
2.题目分析
这道题目和之前做过的最大子段和问题很像，因而想到可以用动态规划方法求解，不一样的是，这里求得是乘积，因此要考虑负数和0的情况。
3.解法一
动态规划的方法一直用的不熟，所以在查资料的过程中发现了一种比较简单的方法，用两个变量maxCurrent和minCurrent表示当前一段内的最大连乘积和最小连乘积，这里之所有要保存最小的因为如果下一个值为负数，那么此时最小的显然就是最大的了。每次都和 maxProduct 和 minProduct比较，并更新他们。
#include <iostream>#include <string>#include <vector>#include <utility>#include <limits.h>using namespace std;class Solution{ public: int maxProduct(int a[], int n){ int maxCurrent, minCurrent, maxProduct, minProduct, i; //maxCurrent 存储当前最大乘积的候选序列 //minCurrent 存储当前最小乘积的候选序列 maxCurrent = minCurrent = 1; maxProduct = a[0]; //数组可能为{0}； minProduct = a[0]; for(i = 0; i < n; i++){ maxCurrent *= a[i]; minCurrent *= a[i]; if(maxCurrent > maxProduct) maxProduct = maxCurrent; if(minCurrent > maxProduct) //负数 * 负数 的情况 maxProduct = minCurrent; if(maxCurrent < minProduct) minProduct = maxCurrent; if(minCurrent < minProduct) minProduct = minCurrent; if(maxCurrent < minCurrent) swap(maxCurrent, minCurrent); if(maxCurrent <= 0) maxCurrent = 1; } return maxProduct; }};int main(int argc, const char *argv[]){ int b[] = {0, 2, 3, -4, -2}; Solution so; cout << so.maxProduct(b, sizeof b/sizeof (int)) << endl; return 0;}4.解法二
动态规划方法。
#include <iostream>#include <string>#include <vector>#include <utility>using namespace std;class Solution{ public: int maxProduct(int a[], int n){ int *maxCurrent, *minCurrent, i, maxProduct; maxCurrent = new int[n]; //maxCurrent[i] a[0]~a[i]的最大连乘积子数组的值 minCurrent = new int[n]; maxCurrent[0] = minCurrent[0] = maxProduct = a[0]; for(i = 1; i < n; i++){ maxCurrent[i] = max(max(a[i], maxCurrent[i-1] * a[i]), minCurrent[i-1] * a[i]); minCurrent[i] = min(min(a[i], maxCurrent[i-1] * a[i]), minCurrent[i-1] * a[i]); maxProduct = max(maxProduct, maxCurrent[i]); } cout << maxProduct << endl; }};int main(int argc, const char *argv[]){ int a[] = {0}; Solution so; so.maxProduct(a, sizeof a / sizeof(int)); return 0;}5.参考资料
https://oj.leetcode.com/problems/maximum-product-subarray/
http://blog.csdn.net/v_july_v/article/details/8701148
1014------算法笔记----------Maximum Product Subarray 最大乘积子数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。