Return the maximum product of any contiguous subarray of exactly length k. Assume
1 <= k <= len(nums) and that all numbers are positive (so a window's product can be
maintained by multiplying in the new element and dividing out the old).
maxSubarrayProduct(nums, k)
Input format: nums | k.
[1, 2, 3, 4], k=2 // → 12 (3*4)
[2, 5, 1], k=1 // → 5
[3, 3, 3], k=2 // → 9
Same shape as maximum sum over fixed windows, but multiplication instead of addition. The naive approach — multiply out the next k elements for every starting position — costs O(k) per window, O(n·k) overall, for the same reason: neighboring windows share k-1 elements, and recomputing from scratch wastes that shared work.
With sums, sliding meant "add the new element, subtract the old," since addition and subtraction are inverses. Multiplication has an inverse too: division. So multiply in the newly entering element and divide out the one that just left. The overlapping middle is untouched, so there's no reason to recompute it.
This only works cleanly because every number is positive. A zero in the window would make dividing it back out undefined. Negative numbers would make division still work mathematically, but the maximum product no longer behaves the way you'd expect — two negatives can multiply into a large positive, which is messier to reason about incrementally. Positivity guarantees dividing out the leaving element exactly undoes its contribution.
Each slide costs O(1) instead of O(k), so the whole algorithm runs in O(n) time and O(1) extra space, versus O(n·k) for brute force. General lesson: whenever an operation has a clean inverse (addition/subtraction, multiplication/division under safe conditions), a fixed-size window can be maintained incrementally instead of rebuilt on every slide.
def max_subarray_product(nums, k):
product = 1
for i in range(k):
product *= nums[i]
best = product
for right in range(k, len(nums)):
product *= nums[right]
product = int(product / nums[right - k])
if product > best:
best = product
return best
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.