Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/152.html
Given an integer array nums
, find a subarray 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.
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 * 104
-10 <= nums[i] <= 10
- The product of any prefix or suffix of
nums
is guaranteed to fit in a 32-bit integer.
Algorithm
The problem can be solved using dynamic programming (DP) with two DP arrays:
- f[i] represents the largest sub-array product within the range of sub-array [0, i] that must contain the number nums[i],
- g[i] represents the smallest sub-array product within the range of sub-array [0, i] that must contain the number nums[i].
During initialization, both f[0] and g[0] are initialized to nums[0], and the rest are initialized to 0.
Starting from the second number of the array, the maximum and minimum values at this time will only be generated between these three numbers:
- f[i-1]*nums[i],
- g[i-1]*nums[i], and
- nums[i].
Therefore, we can use the maximum of the three to update f[i] and the minimum to update g[i]. Then, use f[i] to update the result.
It’s important to note that since the final result may not include the number nums[n-1], f[n-1] is not necessarily
the final solution. The constantly updated result should be returned instead.
Code
-
public class Maximum_Product_Subarray { public class Solution { public int maxProduct(int[] A) { if(A==null || A.length==0) return 0; if(A.length == 1) return A[0]; int max= A[0]; int min = A[0]; int finalmax = A[0]; // just go through and multiply one by one till the end // mark max and min for (int i = 1; i < A.length; i++) { // max possible 1 2 3 int maxp1 = A[i]; // if previous is 0, this one is positive int maxp2 = max * A[i]; int maxp3 = min * A[i]; int maxNotUpdated = max; max = findMax(maxp1, maxp2, maxp3); // min possible 1 2 3 int minp1 = A[i]; // if previous is 0, this one is neg int minp2 = maxNotUpdated * A[i]; int minp3 = min * A[i]; min = findMin(minp1, minp2, minp3); if (max > finalmax) { finalmax = max; } } return finalmax; } public int findMax (int a, int b, int c) { return Math.max( Math.max(a,b), c); } public int findMin (int a, int b, int c) { return Math.min( Math.min(a,b), c); } } } ############ class Solution { public int maxProduct(int[] nums) { int maxf = nums[0], minf = nums[0], res = nums[0]; for (int i = 1; i < nums.length; ++i) { int m = maxf, n = minf; maxf = Math.max(nums[i], Math.max(m * nums[i], n * nums[i])); minf = Math.min(nums[i], Math.min(m * nums[i], n * nums[i])); res = Math.max(res, maxf); } return res; } }
-
// OJ: https://leetcode.com/problems/maximum-product-subarray/ // Time: O(N) // Space: O(1) class Solution { public: int maxProduct(vector<int>& A) { int ans = A[0], N = A.size(), j = 0; while (j < N) { int i = j, prod = 1; while (j < N && A[j] != 0) { prod *= A[j++]; ans = max(ans, prod); } if (j < N) ans = max(ans, 0); while (i < N && prod < 0) { prod /= A[i++]; if (i != j) ans = max(ans, prod); } while (j < N && A[j] == 0) ++j; } return ans; } };
-
class Solution: def maxProduct(self, nums: List[int]) -> int: maxf = minf = res = nums[0] for num in nums[1:]: m, n = maxf, minf maxf = max(num, m * num, n * num) minf = min(num, m * num, n * num) res = max(res, maxf) return res ############ class Solution(object): def maxProduct(self, nums): """ :type nums: List[int] :rtype: int """ maxDP = [0 for _ in range(0, len(nums))] minDP = [0 for _ in range(0, len(nums))] maxDP[0] = nums[0] minDP[0] = nums[0] ans = nums[0] for i in range(1, len(nums)): maxDP[i] = max(minDP[i - 1] * nums[i], nums[i], maxDP[i - 1] * nums[i]) minDP[i] = min(minDP[i - 1] * nums[i], maxDP[i - 1] * nums[i], nums[i]) ans = max(ans, maxDP[i]) return ans
-
func maxProduct(nums []int) int { maxf, minf, res := nums[0], nums[0], nums[0] for i := 1; i < len(nums); i++ { m, n := maxf, minf maxf = max(nums[i], max(nums[i]*m, nums[i]*n)) minf = min(nums[i], min(nums[i]*m, nums[i]*n)) res = max(res, maxf) } return res } func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a < b { return a } return b }
-
function maxProduct(nums: number[]): number { let n = nums.length; let preMax = nums[0], preMin = nums[0], ans = nums[0]; for (let i = 1; i < n; ++i) { let cur = nums[i]; let x = preMax, y = preMin; preMax = Math.max(x * cur, y * cur, cur); preMin = Math.min(x * cur, y * cur, cur); ans = Math.max(preMax, ans); } return ans; }
-
public class Solution { public int MaxProduct(int[] nums) { int maxf = nums[0], minf = nums[0], res = nums[0]; for (int i = 1; i < nums.Length; ++i) { int m = maxf, n = minf; maxf = Math.Max(nums[i], Math.Max(nums[i] * m, nums[i] * n)); minf = Math.Min(nums[i], Math.Min(nums[i] * m, nums[i] * n)); res = Math.Max(res, maxf); } return res; } }
-
impl Solution { pub fn max_product(nums: Vec<i32>) -> i32 { let mut min = nums[0]; let mut max = nums[0]; let mut res = nums[0]; for &num in nums.iter().skip(1) { let (pre_min, pre_max) = (min, max); min = num.min(num * pre_min).min(num * pre_max); max = num.max(num * pre_min).max(num * pre_max); res = res.max(max); } res } }
-
/** * @param {number[]} nums * @return {number} */ var maxProduct = function (nums) { let [f, g, ans] = [nums[0], nums[0], nums[0]]; for (let i = 1; i < nums.length; ++i) { const [ff, gg] = [f, g]; f = Math.max(nums[i], ff * nums[i], gg * nums[i]); g = Math.min(nums[i], ff * nums[i], gg * nums[i]); ans = Math.max(ans, f); } return ans; };