Clean O(n) time O(1) space Java solution


  • 2
    M

    At each step I calculate the minimum and maximum products attainable that include the current number. Then I just keep a running maximum for the whole list.

    public class Solution {
        public int maxProduct(int[] nums) {
            
            int maxProd = nums[0], maxHere = maxProd, minHere = maxProd;
            
            for(int i = 1; i < nums.length; i++){
    
                // maxHere = max of: current number, number * min of previous, number * max of previous
                // minHere = min of: current number, number * min of previous, number * min of previous
                
                int tempMax = maxHere;
                maxHere = Math.max(nums[i],Math.max(maxHere*nums[i],minHere*nums[i]));
                minHere = Math.min(nums[i],Math.min(tempMax*nums[i],minHere*nums[i]));
                maxProd = Math.max(maxProd,maxHere);
            }
            
            return maxProd;
        }
    }

Log in to reply
 

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