Problem:
Find the contiguous subarray within an array (containing at least one number) which has the largest product.For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
Java Code:
public class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int result = nums[0];
int[] maxProduct = new int[nums.length];
int[] minProduct = new int[nums.length];
maxProduct[0] = nums[0];
minProduct[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
int[] tmp = new int[3];
tmp[0] = nums[i];
tmp[1] = nums[i] * maxProduct[i - 1];
tmp[2] = nums[i] * minProduct[i - 1];
Arrays.sort(tmp);
result = Math.max(result, tmp[2]);
maxProduct[i] = tmp[2];
minProduct[i] = tmp[0];
}
return result;
}
}
reference: https://leetcode.com/discuss/41102/share-accepted-dp-java-o-n-solution
没有评论:
发表评论