Try   HackMD

152. Maximum Product Subarray

tags: Dynamic Programming Medium

152. Maximum Product Subarray


Optimal Space & Time Complexity
- Time complexity: O()
- Space complexity: O()

Thoughts & Solutions

YC

Code

Sol

Code

Code

Jessie

Code

Howard

Code

Haoyu

Code

Try 1: Fail, test case = [-2, 3, -4]

var maxProduct = function(nums) { const maxSubarrayProducts = [nums[0]]; const resSubarrayProducts = [nums[0]]; for (let i = 1; i < nums.length; i += 1) { maxSubarrayProducts[i] = Math.max(maxSubarrayProducts[i - 1] * nums[i], nums[i]); resSubarrayProducts[i] = Math.max(resSubarrayProducts[i - 1], maxSubarrayProducts[i]); } return resSubarrayProducts[nums.length - 1]; };

Try 2: https://www.youtube.com/watch?v=0Kpz-ChuQIE

var maxProduct = function(nums) { const maxSubarrayProducts = [nums[0]]; const minSubarrayProducts = [nums[0]]; const resSubarrayProducts = [nums[0]]; for (let i = 1; i < nums.length; i += 1) { maxSubarrayProducts[i] = Math.max(Math.max(maxSubarrayProducts[i - 1] * nums[i], minSubarrayProducts[i - 1] * nums[i]), nums[i]); minSubarrayProducts[i] = Math.min(Math.min(minSubarrayProducts[i - 1] * nums[i], maxSubarrayProducts[i - 1] * nums[i]), nums[i]); resSubarrayProducts[i] = Math.max(resSubarrayProducts[i - 1], maxSubarrayProducts[i]); } return resSubarrayProducts[nums.length - 1]; };

Try 3: Optimize space complexity

var maxProduct = function(nums) { let max = nums[0]; let min = nums[0]; let res = nums[0]; for (let i = 1; i < nums.length; i += 1) { const temp = max; max = Math.max(Math.max(temp * nums[i], min * nums[i]), nums[i]); min = Math.min(Math.min(min * nums[i], temp * nums[i]), nums[i]); res = Math.max(res, max); } return res; };


Live Coding

(name)
// write your code here