/**
Given an integer array nums, find a contiguous non-empty subarray within the
array that has the largest product, and return the product.
The test cases are generated so that the answer will fit in a 32-bit integer.
A subarray is a contiguous subsequence of the array.
Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Constraints:
1 <= nums.length <= 2 * 10⁴
-10 <= nums[i] <= 10
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit
integer.
Related Topics数组 | 动态规划
👍 1781, 👎 0
*/
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] fMax = new int[nums.length];
int[] fMin = new int[nums.length];
System.arraycopy(nums, 0, fMax, 0, nums.length);
System.arraycopy(nums, 0, fMin, 0, nums.length);
for (int i = 1; i < nums.length; i++) {
fMax[i] = Math.max(fMax[i - 1] * nums[i], Math.max(nums[i], fMin[i - 1] * nums[i]));
fMin[i] = Math.min(fMin[i - 1] * nums[i], Math.min(nums[i], fMax[i - 1] * nums[i]));
}
int result = fMax[0];
for (int i = 1; i < nums.length; i++) {
result = Math.max(result, fMax[i]);
}
return result;
}
}
//leetcode submit region end(Prohibit modification and deletion)
