LeetCode [152] Maximum Product Subarray

152. Maximum Product Subarray

Medium

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. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

class Solution { public: int maxProduct(vector<int>& nums) { int n = nums.size(); if(!n) return 0; int ret = nums[0], maxv = nums[0], minv = nums[0]; for(int i=1; i<n; ++i){ int v = nums[i]; int v1 = maxv*v; int v2 = minv*v; maxv = max(v, max(v1, v2)); minv = min(v, min(v1, v2)); ret = max(ret, maxv); } return ret; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

class Solution { public int maxProduct(int[] nums) { int n = nums.length; int maxP = nums[0]; int localMax = nums[0]; int localMin = nums[0]; for(int i=1; i<n; ++i){ int localMax1, localMin1; localMax1 = Math.max(nums[i], Math.max(localMax*nums[i], localMin*nums[i])); localMin1 = Math.min(nums[i], Math.min(localMax*nums[i], localMin*nums[i])); maxP = Math.max(maxP, localMax1); localMax = localMax1; localMin = localMin1; } return maxP; } }