A C++ 11 solution: 3ms, O(n) time complexity and O(1) space complexity


  • 0
    S

    Just like how we solve the maximum subarray problem with Kadane's algorithm 53. Maximum Subarray. Here the exception is that we have to pay attention to the sign of a[k] to compute the max product ending at a[k], termed mp[k], based on mp[k-1].

    Case 1 list item: mp[k] only include a[k]
    Case 2: mp[k] depends on both a[k] and previous elements. In this case, if a[k] > 0, then mp[k] = a[k] * max product ending at a[k-1] = a[k] * mp[k-1]; if a[k] < 0, then mp[k] = a[k] * min product subarray ending at a[k-1].. Therefore, we have to also keep a record of the minimum product ending at each element.

    In total, there are 3 possibilities and the same principle applies to the min product as well. Then, at each element, we can get both the min and max product ending at that element by comparing these 3 possibilities.

    class Solution {
    public:
        // we need to compute both the max and min product ending at a[k]
        // to infer the max of a[k+1] since a[k+1] may be positive or negative
        int maxProduct(vector<int>& nums) {
            int minEndingHere = nums[0];
            int maxEndingHere = nums[0];
            int maxSoFar = nums[0];
            
            for (int i = 1; i < nums.size(); i++){
                std::tie(minEndingHere, maxEndingHere) = std::minmax({nums[i], nums[i] * minEndingHere, nums[i] * maxEndingHere});
                maxSoFar = std::max(maxSoFar, maxEndingHere);
            }
            return maxSoFar;
        }
    };
    

Log in to reply
 

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