grid47 Exploring patterns and algorithms
Oct 22, 2024
5 min read
Solution to LeetCode 152: Maximum Product Subarray Problem
You are given an integer array nums. Find the subarray that has the largest product, and return the product.
Problem
Approach
Steps
Complexity
Input: The input is an integer array nums where each element is an integer between -10 and 10.
Example: nums = [1, 2, -1, 4]
Constraints:
• 1 <= nums.length <= 2 * 10^4
• -10 <= nums[i] <= 10
Output: The output should be an integer representing the largest product of any subarray.
Example: 8
Constraints:
• The product of any subarray will fit within a 32-bit integer.
Goal: To find the maximum product of a subarray, we can track the maximum and minimum products up to the current index.
Steps:
• Initialize two variables, mx and mn, to store the maximum and minimum products so far.
• Initialize a result variable to store the maximum product encountered.
• Iterate through the array, updating mx, mn, and result at each step by considering the current number and its product with the previous mx and mn.
Goal: The input array will always have at least one element.
Steps:
• 1 <= nums.length <= 2 * 10^4
• -10 <= nums[i] <= 10
Assumptions:
• The input array is not empty.
• The product of any subarray will fit within a 32-bit integer.
• Input: nums = [1, 2, -1, 4]
• Explanation: The subarray [1, 2, -1, 4] has the largest product, which is 8.
• Input: nums = [-1, 0, -3, 4]
• Explanation: The subarray [4] has the largest product, which is 4.
Approach: To solve this problem, we will iterate through the array while keeping track of the maximum and minimum products at each step.
Observations:
• When we multiply a negative number by a negative number, it could result in a large positive product.
• By keeping track of both the maximum and minimum products at each index, we can handle the case of negative numbers efficiently.
Steps:
• Initialize two variables mx and mn to 1.
• Iterate through the array nums.
• For each element, update mx and mn by considering the current number, the product of the current number with mx, and the product of the current number with mn.
• Update the result at each step to ensure it holds the largest product encountered so far.
Empty Inputs:
• The input will never be empty.
Large Inputs:
• The solution must handle large inputs efficiently, up to 2 * 10^4 elements.
Special Values:
• Handle negative numbers and zeros correctly.
Constraints:
• The product of any subarray must fit in a 32-bit integer.
intmaxProduct(vector<int>& nums) {
int mx =1, mn =1;
int res = INT_MIN;
for(int i =0; i < nums.size(); i++) {
if(nums[i] <0) swap(mx, mn);
mx = max(nums[i], mx * nums[i]);
mn = min(nums[i], mn * nums[i]);
res = max(res, mx);
}
return res;
}
1 : Function Definition
intmaxProduct(vector<int>& nums) {
Defines the function `maxProduct`, which takes a vector of integers and returns the maximum product of any contiguous subarray.
2 : Variable Initialization
int mx =1, mn =1;
Initializes two variables `mx` and `mn` to 1, representing the maximum and minimum products ending at the current index.
3 : Variable Declaration
int res = INT_MIN;
Declares `res` and initializes it to the minimum integer value (`INT_MIN`) to track the maximum product found during the loop.
4 : Loop Iteration
for(int i =0; i < nums.size(); i++) {
Starts a loop to iterate through the elements of the `nums` vector.
5 : Conditional Check
if(nums[i] <0) swap(mx, mn);
Checks if the current number is negative. If it is, it swaps `mx` and `mn`, as a negative number could flip the product's sign.
6 : Dynamic Programming
mx = max(nums[i], mx * nums[i]);
Updates `mx` to the maximum of the current number itself or the product of `mx` and the current number. This keeps track of the largest product of any subarray ending at the current index.
7 : Dynamic Programming
mn = min(nums[i], mn * nums[i]);
Updates `mn` to the minimum of the current number itself or the product of `mn` and the current number. This helps to track the smallest product, which can be important for handling negative numbers.
8 : Result Update
res = max(res, mx);
Updates the result `res` by comparing it with the current `mx` to keep track of the maximum product encountered so far.
9 : End of Loop
}
Marks the end of the loop that processes each number in the input array.
10 : Return Value
return res;
Returns the final value of `res`, which holds the maximum product of any subarray.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: We iterate through the array once, so the time complexity is linear in the number of elements.
Best Case: O(1)
Worst Case: O(1)
Description: We use a constant amount of space, so the space complexity is O(1).
