Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Constraints
Approach
Links
YouTube
Examples
Input: [2, 3, -2, 4]
Output: 6
Explanation: [2, 3] has the largest product 6.
Input: [-2, 0, -1]
Output: 0
Explanation: The result cannot be 2, because [-2, -1] is not a subarray.
Solutions
/**
* Time complexity : O(N^2) where N is the size of nums. Since we are
* checking every possible contiguous subarray following every element
* in nums we have quadratic runtime.
* Space complexity : O(1) since we are not consuming additional space other
* than two variables: result to hold the final result and accu to
* accumulate product of preceding contiguous subarrays.
*/
class Solution {
public int maxProduct(int[] nums) {
if (nums.length == 0) return 0;
int result = nums[0];
for (int i = 0; i < nums.length; i++) {
int accu = 1;
for (int j = i; j < nums.length; j++) {
accu *= nums[j];
result = Math.max(result, accu);
}
}
return result;
}
}
/**
* Time complexity : O(N)
* Space complexity : O(1)
*/
class Solution {
public int maxProduct(int[] nums) {
int res = nums[0], min = nums[0], max = nums[0];
for(int i = 1; i < nums.length; i++) {
int tmp = max;
int n = nums[i];
max = Math.max(Math.max(n, max*n), min*n);
min = Math.min(Math.min(n, min*n), tmp*n);
if(max > res) res = max;
}
return res;
}
}