Problem
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Solution (Java)
class Solution {
public int maxProduct(int[] arr) {
int ans = Integer.MIN_VALUE;
int cprod = 1;
for (int j : arr) {
cprod = cprod * j;
ans = Math.max(ans, cprod);
if (cprod == 0) {
cprod = 1;
}
}
cprod = 1;
for (int i = arr.length - 1; i >= 0; i--) {
cprod = cprod * arr[i];
ans = Math.max(ans, cprod);
if (cprod == 0) {
cprod = 1;
}
}
return ans;
}
}
Solution (Javascript)
/**
* @param {number[]} nums
* @return {number}
*/
var maxProduct = function(nums) {
if (!nums.length) return 0;
var localMax = 0;
var localMin = 0;
var lastMax = nums[0];
var lastMin = nums[0];
var max = nums[0];
for (var i = 1; i < nums.length; i++) {
localMax = Math.max(lastMax * nums[i], lastMin * nums[i], nums[i]);
localMin = Math.min(lastMax * nums[i], lastMin * nums[i], nums[i]);
max = Math.max(max, localMax);
lastMax = localMax;
lastMin = localMin;
}
return max;
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).