Force deduction 152 question multiplier maximum subarray

152. The largest subarray of multipliers

Problem description ： Give you an array of integers nums , Please find the non empty continuous subarray with the largest product in the array （ The subarray contains at least one number ）, And returns the product of the subarray .
The answer to the test case is 32- position Integers .
Subarray Is a continuous subsequence of an array .

Strategy ： This topic is the topic of dynamic programming , You can solve the answer from the bottom up , Traverse the entire array to calculate the current maximum value with imax For recording , Constantly update and finally solve the answer . Because there are negative numbers in the array , Will change the maximum value to the minimum value , The minimum becomes the maximum , So we need to imin Record the minimum value . When seeking the first i Number of hours ： If the value of this point is positive , Then the maximum value of this point may be the maximum value of the previous number multiplied by the value of this point , Or the value of this point （imax=fmax(imaxnums[i],nums[i])） The minimum value is （imin=fmin(iminnums[i],nums[i]);）; If the value of this point is negative , Exchange the maximum value with the minimum value , Then solve .

Code ：

int maxProduct(int* nums, int numsSize){
    
    int imax=1,imin=1,max=INT_MIN;
    for(int i=0;i<numsSize;i++){
    
        if(nums[i]<0){
      // When a negative number is encountered, the maximum value will become the minimum value , The minimum becomes the maximum   Exchange position at this time 
            int temp=imin;
            imin=imax;
            imax=temp;
        }
        imax=fmax(imax*nums[i],nums[i]);
        imin=fmin(imin*nums[i],nums[i]);
        max=fmax(max,imax); // Compare the past maximum with the maximum at this point 
    }
    return max;
}