To find the maximum product subarray in O(n) time and O(1) space, scan the array once and keep two values at each position: the largest and the smallest product of any subarray ending there. You need the smallest one because multiplying by a negative number turns the most negative product into the most positive one. The answer is the largest “max ending here” you see.<\/p>\n
Given an integer array Start at every index, extend to the right, and keep a running product. Track the best value seen.<\/p>\n This is correct, uses O(1) extra space, and takes O(n^2) time. It is a fine first answer in an interview because it is easy to verify, and it gives you a reference to test the faster version against.<\/p>\n The maximum subarray sum problem (Kadane’s algorithm) keeps one number: the best sum ending at the current index. If it is negative, you drop it and start fresh. Products behave differently. Look at So at every index you remember two things about the subarrays that end there: the largest product and the smallest (most negative) product. A negative number swaps their roles: the old minimum times a negative becomes the new maximum.<\/p>\n For each new number The new maximum is the largest of the three and the new minimum is the smallest. Compute both from the same old values before overwriting either one.<\/p>\n Building a tuple of candidates first avoids the classic bug of updating Take Watch the last row. After Now a zero. For Many write-ups use an equivalent form. If It does the same thing: after the swap, the old minimum sits in There is a second O(n) idea. Within a stretch of the array without zeros, the best subarray is either the whole stretch (an even number of negatives) or it drops a prefix or a suffix up to the first or last negative number. So the best product is always a prefix product or a suffix product of some zero-free stretch. Walk the array from both ends at once, reset the running product to 1 after a zero, and take the maximum over everything you see:<\/p>\n The All four functions above pass these cases, plus 20,000 random arrays of length 1 to 9 with values from -4 to 4, and they agree with the brute force. Good hand-written cases to include:<\/p>\nnums<\/code>, find a contiguous, non-empty subarray with the largest product and return that product (not the subarray). This is LeetCode 152. The array can hold positives, negatives and zeros. Examples:<\/p>\n\n
[2, 3, -2, 4]<\/code> returns 6<\/code> (the subarray [2, 3]<\/code>).<\/li>\n[-2, 0, -1]<\/code> returns 0<\/code>. Neither -2<\/code> nor -1<\/code> beats it, and you cannot skip the zero to combine them because the subarray must be contiguous.<\/li>\n[-2, 3, -4]<\/code> returns 24<\/code>, the whole array: two negatives cancel out.<\/li>\n<\/ul>\nBrute force: O(n^2)<\/h2>\n
def max_product_brute(nums):\n best = nums[0]\n for i in range(len(nums)):\n product = 1\n for j in range(i, len(nums)):\n product *= nums[j]\n best = max(best, product)\n return best\n<\/code><\/pre>\nWhy the maximum product alone is not enough<\/h2>\n
[-2, 3, -4]<\/code>:<\/p>\n\n
3<\/code> is 3<\/code>, because -2 * 3 = -6<\/code> is worse than starting over.<\/li>\n3<\/code>, you would compute 3 * -4 = -12<\/code> and conclude the answer is 3<\/code>.<\/li>\n(-2) * 3 * (-4) = 24<\/code>. The bad-looking -6<\/code> was worth keeping, because the next negative number flips it to 24<\/code>.<\/li>\n<\/ul>\nThe O(n) solution<\/h2>\n
x<\/code>, the best subarray ending at x<\/code> is one of three things:<\/p>\n\n
x<\/code> alone (start a new subarray here, which also handles zeros),<\/li>\nx<\/code> times the previous maximum,<\/li>\nx<\/code> times the previous minimum.<\/li>\n<\/ol>\ndef max_product(nums):\n cur_max = cur_min = result = nums[0]\n for x in nums[1:]:\n candidates = (x, cur_max * x, cur_min * x)\n cur_max, cur_min = max(candidates), min(candidates)\n result = max(result, cur_max)\n return result\n\nprint(max_product([2, 3, -2, 4])) # 6\nprint(max_product([-2, 0, -1])) # 0\nprint(max_product([-2, 3, -4])) # 24\nprint(max_product([-2])) # -2\n<\/code><\/pre>\ncur_max<\/code> and then using the already-changed value to compute cur_min<\/code>. Time is O(n), space is O(1).<\/p>\nA worked trace<\/h3>\n
nums = [2, 3, -2, 4, -1]<\/code>. Both values start at 2<\/code>. Each row shows the state after processing x<\/code>:<\/p>\n\n\n
\n \nx<\/th>\n candidates (x, max*x, min*x)<\/th>\n cur_max<\/th>\n cur_min<\/th>\n result<\/th>\n<\/tr>\n<\/thead>\n \n 2 (start)<\/td>\n –<\/td>\n 2<\/td>\n 2<\/td>\n 2<\/td>\n<\/tr>\n \n 3<\/td>\n 3, 6, 6<\/td>\n 6<\/td>\n 3<\/td>\n 6<\/td>\n<\/tr>\n \n -2<\/td>\n -2, -12, -6<\/td>\n -2<\/td>\n -12<\/td>\n 6<\/td>\n<\/tr>\n \n 4<\/td>\n 4, -8, -48<\/td>\n 4<\/td>\n -48<\/td>\n 6<\/td>\n<\/tr>\n \n -1<\/td>\n -1, -4, 48<\/td>\n 48<\/td>\n -4<\/td>\n 48<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n 4<\/code>, the maximum is only 4<\/code>, but the minimum -48<\/code> is the product of the whole prefix 2 * 3 * -2 * 4<\/code>. The final -1<\/code> flips it into 48<\/code>, the answer. A solution that tracked only the maximum would return 6<\/code>.<\/p>\n[-2, 0, -1]<\/code>: start at -2<\/code>. At 0<\/code> every candidate is 0<\/code>, so max and min both become 0<\/code> and the old product is wiped out. At -1<\/code> the candidates are -1, 0, 0<\/code>, so max is 0<\/code>, min is -1<\/code>, and the result stays 0<\/code>. No special zero handling is needed because “x alone” is always a candidate.<\/p>\nVariant: swap instead of computing three candidates<\/h2>\n
x<\/code> is negative, swap the max and min first, then multiply:<\/p>\ndef max_product_swap(nums):\n cur_max = cur_min = result = nums[0]\n for x in nums[1:]:\n if x < 0:\n cur_max, cur_min = cur_min, cur_max\n cur_max = max(x, cur_max * x)\n cur_min = min(x, cur_min * x)\n result = max(result, cur_max)\n return result\n<\/code><\/pre>\ncur_max<\/code>, so multiplying by a negative x<\/code> gives the larger value. The three-candidate version is harder to get wrong, so it is the safer one to write under pressure.<\/p>\nAnother way: prefix and suffix products<\/h2>\n
def max_product_prefix_suffix(nums):\n best = nums[0]\n prefix = suffix = 1\n for i in range(len(nums)):\n prefix = (prefix or 1) * nums[i]\n suffix = (suffix or 1) * nums[-1 - i]\n best = max(best, prefix, suffix)\n return best\n<\/code><\/pre>\n(prefix or 1)<\/code> trick restarts the product after a zero. This version is short, but the reasoning behind it is harder to explain, so the max\/min version is usually the better choice in an interview.<\/p>\nTest it against the brute force<\/h2>\n
cases = [\n ([2, 3, -2, 4], 6),\n ([-2, 0, -1], 0),\n ([-2, 3, -4], 24),\n ([0, 2], 2),\n ([-2, -3, -4], 12),\n ([-3], -3), # single negative element\n ([-1, -1], 1),\n ([0, 0], 0),\n ([1, 0, -1, 2, 3, -5, -2], 60),\n]\nfor nums, expected in cases:\n assert max_product(nums) == expected, nums\nprint(\"all passed\")\n<\/code><\/pre>\nCommon mistakes<\/h2>\n
\n
[-2, 3, -4]<\/code>, where the answer depends on a negative product you would have thrown away.<\/li>\ncur_max<\/code> and then computing cur_min<\/code> from the new cur_max<\/code> gives wrong results. Compute both from the old values.<\/li>\nnums[0]<\/code>. If you start result<\/code> at 0, an input like [-3]<\/code> returns 0<\/code> instead of -3<\/code>.<\/li>\nWhat an interviewer may ask next<\/h2>\n
\n
i<\/code> is a subarray ending at i - 1<\/code> extended by nums[i]<\/code>, or just nums[i]<\/code>. The product of the extended one is monotone in the old product: if nums[i]<\/code> is positive, the largest old product gives the largest new one; if negative, the smallest does. So only the extremes matter.<\/li>\nresult<\/code> improves). The extra state does not change the complexity.<\/li>\n