code.ashish.me

Atom feed

Recently added: 02 Count Of Subset Sum, 416 Partition Equal Subset Sum, 01 Subset Sum, 518 Coin Change 2, 983 Minimum Cost For Tickets

152 Maximum Product Subarray

/**
 * 
 * Ashish Patel
 * e: ashishsushilPatel@gmail.com
 * w: https://ashish.me
 *
 */

/* 
  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 product 6.
  Example 2:

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

function maximumProductSubarray(value) {
  let min = [1];
  let max = [1];
  for (let index = 0; index < value.length-1; index++) {
    const currentNum = value[index]
    if(value[index] < 0) {
      max[index + 1] = Math.max(currentNum*min[index],currentNum)
      min[index + 1] = Math.min(currentNum*max[index],currentNum)
    } else {
      max[index + 1] = Math.max(currentNum*max[index],currentNum)
      min[index + 1] = Math.min(currentNum*min[index],currentNum)
    }
  }
  max[0] = -Infinity
  return Math.max(...max)
}

console.table(maximumProductSubarray([2,3,-2,4]))
/* 
test('maximum Product Subarray', () => {
  expect(maximumProductSubarray([2,3,-2,4])).toEqual(6)
}); */

Created 2020-02-23T08:56:10+00:00, updated 2020-03-02T13:08:39+00:00 · History · Edit