题目：

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.

解题思路：

采用动态规划的方法。由于存在正负号，而负负得正，故需同时记录最大值和最小值。 用lastmax记录前一个最大值，lastmin记录前一个最小值，curmax记录当前最大值，curmax记录当前最小值（寻找局部最优） max记录全局最优解

代码：

int maxProduct(int* nums, int numsSize) { int max=nums[0]; int lastmax=nums[0]; int lastmin=nums[0]; int curmax,curmin; int temp1; int temp2; if(numsSize==1) return nums[0]; for(int i=1;i<numsSize;i++) { temp1=lastmax*nums[i]; temp2=lastmin*nums[i]; curmax=temp1>temp2?temp1:temp2; curmax=curmax>nums[i]?curmax:nums[i]; curmin=temp1>temp2?temp2:temp1; curmin=curmin>nums[i]?nums[i]:curmin; max=max>curmax?max:curmax; lastmax=curmax; lastmin=curmin; } return max; }