Leetcode: Maximum Product Subarray

Maximum Product Subarray

My Submissions

Total Accepted: 46701 Total Submissions: 224496 Difficulty: Medium

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.

Subscribe to see which companies asked this question

Hide Tags

 Array Dynamic Programming

Show Similar Problems

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

DP:

Using max, min to store the previous maximal and minimal produce, and a gmax to keep the biggest one. 

To calculate the max and min, we will encounter several cases:

for nums[i] we have: CASE A; CASE B; CASE C;

FOR max and min, we have:

case 1~case4;

see figure below:

/////////////////////////////////////////////////////////////////

//codes

class Solution {

 public:

        int maxProduct(vector<int>& nums) {

               //check input

               if (nums.size() == 1)return nums[0];

               int ma = nums[0], mi = nums[0], gMax = nums[0];

               for (int i = 1; i<nums.size(); i++){

                      if (nums[i]>0){ //case A  

                            if (ma<0){ mi = nums[i] * mi; ma = nums[i]; } //case 1

                            else if (mi>0) { mi = nums[i]; ma = ma*nums[i]; }//case 2

                            else if (mi == 0 || ma == 0) { mi = nums[i]; ma = nums[i]; }//case 3

                            else { mi = nums[i] * mi; ma = nums[i] * ma; }//case 4

                      }

                      else if (nums[i]<0){ //CASE B

                            if (ma<0){ ma = nums[i] * mi; mi = nums[i]; }

                            else if (mi>0) { mi = nums[i] * ma; ma = nums[i]; }

                            else if (mi == 0 || ma == 0) { mi = nums[i]; ma = nums[i]; }

                            else { int tmp = mi; mi = nums[i] * ma; ma = nums[i] * tmp; }

                      }

                      else{ // is 0  //CASE C

                            mi = 0; ma = 0;

                      }

                      gMax = gMax<ma ? ma : gMax;

               }

               return gMax;

        }

 };