Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array
the contiguous subarray
[2,3,-2,4]
,the contiguous subarray
[2,3]
has the largest product = 6
.Solution:
The continuous element does not need to be adjacent.
For example, [-2, 2, -5] outputs 10, which is - 2 x 5.
At each step, we keep the max and min of the product.
The reason to keep min is because min could be a negative number and negative times negative is positive, which might be a max.
The max at this step is the maximum of max * nums[i], min * nums[i], and nums[i].
The time complexity is O(n) and the space complexity is O(1).
Code:
public class Solution { public int maxProduct(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int max = 1; int min = 1; int result = nums[0]; for (int num : nums) { int tmp = max; max = Math.max(num, Math.max(num * max, num * min)); min = Math.min(num, Math.min(num * tmp, num * min)); result = Math.max(result, max); } return result; } }