152. Maximum Product Subarray

The idea behind is to keep two variables. One is to hold the maximum product and the other is to hold the minimum product. If there is a positive number, the maximum product gets larger and the minimum product gets smaller. On the other hand, fi there is a negative number, the maximum product and the minimum product will be swapped.

1:  class Solution {  
2:  public:  
3:    int maxProduct(vector<int>& nums) {  
4:      int max_product = nums[0];  
5:      int min_product = nums[0];  
6:      int ret = nums[0];  
7:      for (int i = 1; i < nums.size(); i++) {  
8:        if (nums[i] >= 0) {  
9:          max_product = max(max_product*nums[i], nums[i]);  
10:          min_product = min(min_product*nums[i], nums[i]);  
11:        } else {  
12:          int tmp = max_product;  
13:          max_product = max(min_product*nums[i], nums[i]);  
14:          min_product = min(tmp*nums[i], nums[i]);  
15:        }  
16:        ret = max(max_product, ret);  
17:      }  
18:      return ret;  
19:    }  
20:  };