Share my simple Java code with explanation


  • 0
    M
    /*
        define max[i]/min[i] as the max/min product of subarray ENDING WITH a[i].
        max[i] = max(max[i-1]*a[i], min[i-1]*a[i], a[i])
        min[i] = min(max[i-1]*a[i], min[i-1]*a[i], a[i])
        we need to find max(max[i]), for 0 <= i < a.length
    */
    public class Solution {
        public int maxProduct(int[] nums) {
            if (nums == null || nums.length == 0) { return 0; }
            int max = nums[0];
            int prevMin = nums[0], prevMax = nums[0];
            for (int i = 1; i < nums.length; ++i) {
                int prod1 = prevMin * nums[i];
                int prod2 = prevMax * nums[i];
                prevMin = Math.min(nums[i], Math.min(prod1, prod2));
                prevMax = Math.max(nums[i], Math.max(prod1, prod2));
                max = Math.max(prevMax, max);
            }
            return max;
        }
    }

  • 0
    M

    Could you share an explanation? Why does this work?


  • 0
    M

    /* define max[i]/min[i] as the max/min product of subarray ENDING WITH a[i]. max[i] = max(max[i-1]*a[i], min[i-1]*a[i], a[i]) min[i] = min(max[i-1]*a[i], min[i-1]*a[i], a[i]) we need to find max(max[i]), for 0 <= i < a.length */


Log in to reply
 

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