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; } } |
No comments:
Post a Comment