tatumalenko
2/21/2019 - 7:02 AM

152. Maximum Product Subarray

https://leetcode.com/problems/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.
maxSubarrayProduct.cpp
content_copyfile_download
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int len = nums.size();
        int maxhere = nums.at(0);
        int minhere = nums.at(0); // Needed in case lowest number becomes largest 
                                  // from negative number multiplication
        int maxsofar = nums.at(0);
        
        for (int i = 1; i < len; ++i) {
            // If multiplying by negative, the min/max switch.
            if (nums.at(i) < 0)
                swap(maxhere, minhere);
            
            // Either the contiguous sum is better or the current value will
            // be used to restart contiguous check.
            maxhere = max(nums.at(i), maxhere*nums.at(i));
            minhere = min(nums.at(i), minhere*nums.at(i));
            
            // 
            maxsofar = max(maxhere, maxsofar);
        }
        
        return max(maxsofar, maxhere);
    }
};