C++ solution. 4ms explained.

  • 4
    int maxProduct(vector<int>& nums) {
        if(nums.empty()) {
            return 0;
        int currentMax = nums[0];
        int currentMin = nums[0];
        int maxProduct = nums[0];
        for(size_t i = 1; i < nums.size(); ++i) {
            //calculate our new possibilities for this round
            int p1 = currentMax * nums[i];
            int p2 = currentMin * nums[i];
            //our currentMax will be either p1 or p2 or nums[i] whichever is bigger
            currentMax = max(nums[i], max(p1, p2));
            //our currentMin will be either p1 or p2 or nums[i] whichever is smaller
            currentMin = min(nums[i], min(p1, p2));
            //our maxProduct will be our currentMax or our maxProduct, whichever is bigger.
            maxProduct = currentMax > maxProduct ? currentMax : maxProduct;
        return maxProduct;

    So all you care about is keeping track of the highest possible max so far.

    Apart from that you need to keep track of your highest possible in the subarray. Lookup kadanes algorithm for this.

    Since we can have negative numbers you need to keep track of your lowest possible in the subarray.
    This is because your lowest which might be negative can become your highest when multiplied by a negative number.

    By keeping track of these both you have your highest and lowest which can invert themselves.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.