【C语言】LeetCode 152. 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

.

解题思路：

采用动态规划的方法。由于存在正负号，而负负得正，故需同时记录最大值和最小值。 用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;
}