Accepted Java solution, O(n) time


  • 2
    W

    Instead of maintaining 1 array (as is the case with Maximum Sum Subarray problem), we should maintain 2 arrays - one for max and one for min. This is because min value could have the lowest negative value, which could later turn out to become maximum when multiplied by another negative number. Very good explanation of the same is given in LeetCode's official solution.

    Below is my code :-

    public class Solution {
        public int maxProduct(int[] nums) {
            if(nums.length == 0)
                return 0;
            int maxIndex = 0;
            int[] max = new int[nums.length];
            int[] min = new int[nums.length];
            max[0] = nums[0];
            min[0] = nums[0];
            for(int i = 1; i < nums.length; i++) {
                int a = nums[i];
                int b = nums[i] * max[i - 1];
                int c = nums[i] * min[i - 1];
                max[i] = a > b ? (a > c ? a : c) : (b > c ? b : c);
                min[i] = a < b ? (a < c ? a : c) : (b < c ? b : c);
                if(max[i] > max[maxIndex])
                    maxIndex = i;
            }
            return max[maxIndex];
        }
    }

  • 0
    H

    you don't need two arrays. two tmp variables are enough


  • 0
    Y

    I can't make it, can you show me the solution?


Log in to reply
 

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