Maximum Product Subarray

Maximum Product Subarray

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.

Solutions

🧠 Cpp

#include <functional>
class Solution
{
public:
    int maxProduct(vector<int>& nums)
    {
        //case for 1 number
        if(nums.size() == 1)
            return nums[0];

        //erase consecutive 1 an -1
        bool removed_ones = true;
        if(nums.size() > 50)
        while(removed_ones)
        {
            removed_ones = false;
            for(auto iter = nums.begin()++; iter != nums.end()-2;)
            {
                int val = *iter;
                if(
                    (val == 1 || val == -1) &&
                        val == *next(iter)  ||
                    (val == 1 || val == -1) && 
                        (*next(iter) == val*-1 && *prev(iter) ==  val*-1 ) )             
                {
                    iter = nums.erase(iter);
                    removed_ones = true;
                }
                else
                   ++iter;

            }
        }

        int max = 0;
        for(auto begin_iter = nums.begin(); begin_iter < nums.end(); ++begin_iter)
        {
            int product = *begin_iter,
                new_product = *begin_iter;

            for(auto current_iter = next(begin_iter);
                current_iter < nums.end();
                current_iter++)
            {
                new_product *= *current_iter;
                if(new_product > product)
                    product = new_product;
            }

            if(product > max) max = product;
        }

        return max;
    }
};