leecode 解题总结：152. Maximum Product Subarray

#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*问题: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.分析:找到最大连续乘积的子数组，至少包含一个元素。之前最大连续和的子数组采用，如果累加和<0,就令结果为当前元素；否则令结果=当前元素+累加和这里可以采用：如果累乘和<0,就令结果为当前元素，但是似乎不行，如果当前元素也是负数，可能结果为正。2 3 -2 -4直接令结果dp[i+1]=dp[i]或者不断累乘得到每个dp[i]是数组A[1..i]元素累乘的结果一种暴力破解方法：不断罗列起点和终点，计算起点和终点的乘积，时间复杂度为O(n^2)另一种方法基于分治：把区间分成左边和右边部分，计算左边乘积的最大值left，计算右边乘积的最大值right，最终的最大值在(left , right , left*right)中产生但是由于如果仅仅依靠当前计算结果舍弃掉某些数值部分，可能会导致最终结果不对。另外如果乘数中有的为0，则递归乘以就有问题，除非将这些0的部分用1代替，麻烦如果用dp[i]表示A[0...i]元素中的最大乘积，输入:4(数组元素个数)2 3 -2 442 3 -2 -452 3 0 -1 -83-2 -3 7输出:624842关键解法：1 直到数组元素A[0..i]的最大乘积来源于:之前的乘积minPre * A[i],maxPre * A[i], A[i]选择三者中的最大值和最大乘积比较，决定是否更新，然后令minPre为三者中的最小值，maxPre为三者中的最大值2			maxHere = max( max( minPre * nums.at(i) , maxPre * nums.at(i) ) , nums.at(i) );			minHere = min( min( minPre * nums.at(i) , maxPre * nums.at(i) ) , nums.at(i) );			result = max(result , maxHere);			minPre = minHere;			maxPre = maxHere;*/class Solution {public:    int maxProduct(vector<int>& nums) {        if(nums.empty())		{			return 0;		}		int size = nums.size();		int result = nums.at(0);		int minPre = nums.at(0);		int maxPre = nums.at(0);		int minHere = 0;		int maxHere = 0;		for(int i = 1 ; i < size ; i++)		{			maxHere = max( max( minPre * nums.at(i) , maxPre * nums.at(i) ) , nums.at(i) );			minHere = min( min( minPre * nums.at(i) , maxPre * nums.at(i) ) , nums.at(i) );			result = max(result , maxHere);			minPre = minHere;			maxPre = maxHere;		}		return result;    }};void process(){	 vector<int> nums;	 int value;	 int num;	 Solution solution;	 vector<int> result;	 while(cin >> num )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 int maxNum = solution.maxProduct(nums);		 cout << maxNum << endl;	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}/*    int maxProduct(vector<int>& nums) {        if(nums.empty())		{			return 0;		}		int size = nums.size();		vector<long long> products;//products[i]表示A[0...i]的乘积		long long product = 1;		for(int i = 0 ; i < size ; i++)		{			product *= nums.at(i);			products.push_back(product);		}		//不断罗列起点和终点，计算乘积		long long maxProduct = INT_MIN;		long long curProduct = 1;		for(int i = 0 ; i < size ; i++)		{			for(int j = i ; j < size; j++)			{				//计算A[i...j]的乘积				if(i >= 1)				{					if( 0 != products.at(i  - 1) )					{						curProduct = products.at(j) / products.at(i  - 1);						}					//比如0 1 2 3,求得是p[1..3]，是6,之前的0导致其发生变化，因此需要重新计算					else					{						curProduct = 1;						for(int k = i ; k <= j ; k++)						{							curProduct *= nums.at(k);							if(0 == curProduct )							{								break;							}						}					}				}				// i = 0				else				{					curProduct = products.at(j);				}				maxProduct = max(maxProduct , curProduct);			}		}		return ( (int)maxProduct );    }*/