#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 );    }*/