[DP][Subarray] Maximum Product Subarray

1. Example

s= [2,3,-2,4]
the contiguous subarray [2,3] has the largest product = 6

2. Implementation
Q1: what if negative * negative become the largest?
A1: keep an lastNegativeNumber to record the previous product is negative, if positive, we just erase it and assign 0 to it
Q1: subarray + maximum = > local , global ? what is global here? what is local here?
A1: global : maximum subarray product
local: previous product * current , current
e.g., [1,-2,3]
i=1
local = max(1*-2,-2) = -2
lastNeg = -2
global = max(1, -2)   =  1
i=2
local =max( -2*3,3)      =  3
lastNeg = -6
global = max(1,3)     =  3
Ans: the largest product is 3 form [3]

e.g., [1,-2,3,-4]
i =3
local = max(3*-4, -4) = -4
if ( curr < 0 && lastNeg <0)
  lastNeg * cur =  -6*-4 =24
  local = max(-4, 24) = 24
global = max(3,-4) = 3   X
global = max(24, 3) = 24
Ans: the largest product is 24 form [1,-2,3,-4]

Input:[-2,3,-4]
Output:16
Expected:24

// NOTE: snippet
int local_unchanged_copy = local;

local = Math.max( Math.max(local*nums[i], nums[i]), min_local*nums[i] );

min_local = Math.min( Math.min(nums[i]*local_unchanged_copy, nums[i]), nums[i]*min_local );

public int maxProduct (int[] nums)
{




     // validate the input
     if (  nums == null || nums.length == 0 )
     {
         return 0;
     }


     

     int global = nums[0];
     int local = nums[0];
     //int lastNeg = 0;
     // NOTE: min local = lastNeg
     int min_local = num[0];
     for (int i =1; i< nums.length ; i++)
     {
          //local = Math.max(local*nums[i], nums[i]);
          //lastNeg =(local < 0) ? local:0;
          //if ( nums[i] < 0 && lastNeg < 0 )
          //{
          //      local = Math.max(lastNeg*nums[i], local);
          //}

          int local_unchanged_copy = local;
          local = Math.max(  Math.max(local*nums[i], nums[i]),  min_local*nums[i]  );   
          min_local = Math.min(  Math.min(nums[i]*local_unchanged_copy, nums[i]),  nums[i]*min_local  );   
          global = Math.max(local, global);
     }
 



     return global;


}

3. Similar Ones
Subarray (continuous) + maximum => DP
(M) Best Time to Buy and Sell Stock
(M) Maximum Subarray
(M) Product of Array Except Self