Maximum subarray product - brute force, and also dynamic programming - 4/26/2018 10:00 PM mock interview

MaximumSubarrayProduct.js

var _ = require('underscore');




/* 
Your previous Plain Text content is preserved below:

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:



Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest sum = 6.
Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
 */
/*

max = a1*a2...*an 

start = 0
end = 0, 1, 2, 3,
2, [0,0]
2,3
2, 3, -2
2, 3, -2, 4


start 1
end= 1,2,3

start=2
end=2,3

start=3
end =3
*/


// Input: [2,3,-2,4]
// 2,

var func = function(arr) {
  
  var max = 0;
  for(var i=0; i<arr.length; i++) {
    
    var temp_max = arr[i];
    if(temp_max > max) {
        max = temp_max;
      
    }
    
    for(var j=i+1; j<arr.length; j++) {
      
      // at i, i+1,.., j  [2, 3, -2, 4],i = 0, j = 3
      // temp_max = 1
      // temp_max = 1*2*3
      // temp_max = 1*2*3*-2
      // temp_max = 1*2*3*-2*4
      temp_max *= arr[j];
      
      if(temp_max > max) {
        max = temp_max;      
      }  
    }  
  }
  
  return max;  
};

// var a = func([-2,10,-2, 10, -2]);

// subproblem - subarray end at positon i = 1, 
//   max Product [-2, 10] - 10 
//   min product [-2, 10] = -20

// dynamic program - 
//   subarray end at position i = 2, 
//     max product [-2, 10, -2], max product = 40
                                
//  formula to do calucation:
//  dp_max[i] = Max
//  dp_min[i] = Min(arr[i], arr[i] * dp_max[i - 1], arr[i] * dp_min[i - 1])

// max = max(dp_Max[0], dp_max[1], ...., dp_max[n-1])

var dp_func = function(arr) {  
  var dp_min = new Array(arr.length);
  var dp_Max = new Array(arr.length); 
  
  dp_min[0] = arr[0];
  dp_Max[0] = arr[0];
  
  var global_max = dp_Max[0]; 
  
  for(var i = 1; i < arr.length; i++)
  {  
    dp_Max[i] = Math.max(arr[i], arr[i] * dp_Max[i-1], arr[i] * dp_min[i - 1]);
    dp_min[i] = Math.min(arr[i], arr[i] * dp_Max[i-1], arr[i] * dp_min[i - 1]);                     

    if(dp_Max[i] >  global_max) {
      global_max = dp_Max[i];
    }    
  }
  
  return global_max;  
};

var a = dp_func([-2,10,-2, 10, -2]);
console.log(a);