Simple 4ms C++ solution


  • 1
    J
    int maxProduct(vector<int>& nums) {
        int lastMin = nums.front(), lastMax = nums.front(), result = lastMax;
        for(int i = 1; i<nums.size(); i++) {
            int tempMin = lastMin, tempMax = lastMax;
            lastMin = min(nums[i], min(tempMin * nums[i], tempMax * nums[i]));
            lastMax = max(nums[i], max(tempMin * nums[i], tempMax * nums[i]));
            result = max(result, lastMax);
        }
        
        return result;
    }

  • 1
    A

    Yes, your code is quite succinct, but I cannot clearly understand the idea behind your code. Would you please detail your idea? If you would, I will be very appreciated.


  • 0
    J

    My code works perfectly same as what other people do. What I did here is just optimize space complexity. Every iteration, we need to look into min & max values calculated just before. So, I just used two variables (lastMin and lastMax) instead of using n size of array. (Actually, 2n because we need to keep track of minimum and maximum values)


  • 0
    A

    Yes, I have noticed the similar code other people submitted. But I am really focused on is how this algorithm is derivated or develped, i.e. what inspired you to use lastmin and lastmax to solve this problem at the same time? Would you please share your prolem-solving idea?


Log in to reply
 

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