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.

Analyse: brute force

Time limit exceeded.

 1 class Solution {
 2 public:
 3     int maxProduct(vector<int>& nums) {
 4         if (nums.empty()) return 0;
 5         
 6         int result = INT_MIN;
 7         for (int i = 0; i < nums.size(); i++) {
 8             int tempProduct = 1;
 9             for (int j = i; j < nums.size(); j++) {
10                 tempProduct *= nums[j];
11                 result = max(result, tempProduct);
12             }
13         }
14         return result;
15     }
16 };

Analyse: Dive into the features of the array, it asks us to compute the product of a continuous subarray. Every element has two choices: combine with its former element, and not combine with its former element. Consider the index i, suppose the former maximum is preMax, and the former minimum is preMin. Combine with former elements may update the value of preMax or preMin, and do not combine with former elements may also update the value of preMax or preMin.

Do remember that after updating the newMin/newMax, we can not calculate the newMax/newMin with the newMin/newMax.

Runtime: 6ms

 1 class Solution {
 2 public:
 3     int maxProduct(vector<int>& nums) {
 4         if (nums.empty()) return 0;
 5         
 6         int preMin = nums[0], preMax = nums[0];
 7         int result = preMax;
 8         for (int i = 1; i < nums.size(); i++) {
 9             int newMin = min(preMin * nums[i], min(preMax * nums[i], nums[i]));
10             preMax = max(preMin * nums[i], max(preMax * nums[i], nums[i]));
11             preMin = newMin;
12             result = max(preMax, result);
13         }
14         return result;
15     }
16 };