LeetCode : 152. Maximum Product Subarray 最大乘积子数组

绝地灬酷狼 2021-06-24 16:10 452阅读 0赞

**试题：**  
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: \[2,3,-2,4\]  
Output: 6  
Explanation: \[2,3\] has the largest product 6.  
Example 2:

Input: \[-2,0,-1\]  
Output: 0  
Explanation: The result cannot be 2, because \[-2,-1\] is not a subarray.  
**代码：**  
如果等于0显然要重新进行统计，所以我们可以用0作为区间分割点。  
在两个0之间，如果第一次出现负数，那么应该重新进行统计，如果第二次出现负数，说明两个负数能够为正。所以我们需要一个变量记录负数乘积，等第二次出现时对其进行纠正。  
其实对于两个0之间如果存在偶数个负数，那么整个区间就是最大值，如果是奇数，那么就要抛弃前一个或者后一个负数。

class Solution {
        public int maxProduct(int[] nums) {
            //nums = new int[]{1,-2,1,-2,1,-2,1,-2,1,-2,100};
            int max = nums[0];
            int pro=1,neg=1;
            
            for(int num : nums){
                if(num>0){
                    max = Math.max(max, pro*num);
                    pro *= num;
                    neg *= num;
                }else if(num<0){
                    max = Math.max(max, neg*num);
                    int tmp = pro;
                    pro = Math.max(neg*num, 1);
                    neg = tmp*num;
                }else{
                    max = Math.max(max, 0);
                    pro = 1;
                    neg = 1;
                }
                //System.out.println(neg);
            }
            return max;
        }
    }

neg:  
1  
\-2  
\-2  
\-2  
\-2  
\-8  
\-8  
\-8  
\-8  
\-32  
\-3200