C++ dp solution using O(1) extra space.


  • 3
    C
    int maxProduct(vector<int>& nums) {
        int curMax, curMin, res;
        curMax = curMin = res = nums[0];
        for (unsigned int i=1; i<nums.size(); i++) {
            int tmp = curMin;
            curMin = min(nums[i], min(curMax*nums[i], curMin*nums[i]));
            curMax = max(nums[i], max(curMax*nums[i], tmp*nums[i]));
            res = max(res, curMax);
        }
        return res;
    }

  • 0

    You need, at least check if the vector is empty or not. Anyway, the code is very neat and expressive!


  • 0
    C

    Yes, that's true, vector should be checked first! thanks


  • 0

    For this solution, I have some doubts in mind:

    1. curMax/curMin may not be contiguous with i, so I don't think we can safely multiply nums[i] with curMax or curMin. (this is the case when there is 0 in middle, it partitions the array)
    2. And what happens if there is 0 at start of array, then max and min both are ZERO.
      Did I miss anything?

  • 0

    Yes, you did miss something. If it becomes 0, then when comes to next number, you will start over: curMin=min(nums[i], 0). you see that curMin will be negative or zero.


Log in to reply
 

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