152. 乘积最大子数组

 1 //1、如果nums[i]为正
 2 // min_val[i] = min(min_val[i - 1] * nums[i],nums[i]);
 3 // max_val[i] = max(max_val[i - 1] * nums[i],nums[i]);
 4 
 5 //2、如果nums[i]为负
 6 // min_val[i] = min(max_val[i - 1] * nums[i],nums[i]);
 7 // max_val[i] = max(min_val[i - 1] * nums[i],nums[i]);
 8 class Solution 
 9 {
10 public:
11     int maxProduct(vector<int>& nums) 
12     {
13         int n = nums.size();
14         vector<int> max_val(n,0);
15         vector<int> min_val(n,0);
16         min_val[0] = nums[0];
17         max_val[0] = nums[0];
18         int res = nums[0];
19         for(int i = 1;i < n;i ++)
20         {
21             if(nums[i] > 0)
22             {
23                 min_val[i] = min(min_val[i - 1] * nums[i],nums[i]);
24                 max_val[i] = max(max_val[i - 1] * nums[i],nums[i]);
25             }
26             else if(nums[i] < 0)
27             {
28                 min_val[i] = min(max_val[i - 1] * nums[i],nums[i]);
29                 max_val[i] = max(min_val[i - 1] * nums[i],nums[i]);
30             }
31             res = max(res,max_val[i]);
32         }
33         return res;
34     }
35 };