DP java Solution with Explanation


  • 0
    N
    /*
    f(n) : max positive value in stage n
    g(n): min negative value in stage n
    
    - nums[n] > 0
      f(n) =  nums[n] ,         when f(n-1) ==0
           = f(n-1) * nums[n] , when f(n-1) >0;
      g(n) = g(n-1)* nums[n]
    
    - nums[n] < 0
      similar 
    
    - nums[n] = 0
       f(n)  = 0
       g(n) = 0
    
    the max product will be the max f(n) value
    */
        public class Solution {
            public int maxProduct(int[] nums) {
                int[] productP = new int[nums.length];// the max positive product
        		int[] productN = new int[nums.length];// the min negative product
        		int max = nums[0];
        
        		if (nums[0] > 0) {
        			productP[0] = nums[0];
        		} else {
        			productN[0] = nums[0];
        		}
        
        		for (int i = 1; i < nums.length; i++) {
        			if (nums[i] > 0) {
        				productP[i] = (productP[i-1] == 0 ? nums[i] : productP[i-1] * nums[i]);
        				productN[i] = productN[i-1] * nums[i];
        			} else if (nums[i] < 0) {
        				productP[i] = productN[i-1] * nums[i];
        				productN[i] = (productP[i-1] == 0 ? nums[i] : productP[i-1] * nums[i]);
        			} else {
        				productP[i] = 0;
        				productN[i] = 0;
        			}
        			if (productP[i] > max)
        				max = productP[i];
        		}
        
        		return max;
            }
        }

  • 0
    X

    This solution is not complete.

    Need to run the same solution from the end of the array toward the beginning of the array for a second time to get correct answer.

    Try this array
    int[] testArray = {6,-3,2,-5,7,-7,2,-11,5,-13,5, -17, 9};


Log in to reply
 

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