Description
Submission
class Solution {
public:
int maxProduct(vector& nums) {
if(nums.empty()) return 0;
int localMin = nums[0], localMax = nums[0], globalMax = nums[0];
for(int i = 1; i < nums.size(); ++i) { int tmp = max(nums[i], max(localMax * nums[i], localMin * nums[i])); localMin = min(nums[i], min(localMin * nums[i], localMax * nums[i])); localMax = tmp; globalMax = max(localMax, globalMax); } return globalMax; }
};
References
- https://medium.com/@aliasav/algorithms-maximum-product-subarray-b09e520b4baf
- https://www.wikiwand.com/en/Maximum_subarray_problem
- https://leetcode.com/problems/maximum-product-subarray/discuss/841167/C%2B%2B-Super-Simple-and-Clean-Solution-O(n)
- https://www.geeksforgeeks.org/maximum-product-subarray/