Maximum Product Subarray
31%
Accepted
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
Have you met this question in a real interview?
Yes
Example
For example, given the array
[2,3,-2,4]
, the contiguous subarray [2,3]
has the largest product = 6
./**
* @param nums: an array of integers
* @return: an integer
*/
public int maxProduct(int[] nums) {
// write your code here
int min = nums[0], max = nums[0], product = nums[0];
for(int i = 1; i < nums.length; i++){
int maxCopy = max;
max = Math.max(max*nums[i], Math.max(min*nums[i], nums[i]));
min = Math.min(maxCopy*nums[i], Math.min(min*nums[i], nums[i]));
product = Math.max(product, max);
}
return product;
}
}
No comments:
Post a Comment