This article is organized by oavoservice in an interview review style: clearly explaining the logic with the shortest path and providing a code template ready for memorization.
Problem (Restated)
Given an integer array nums, find a contiguous subarray that has the largest product, and return the product.
Example:
- Input:
[1, 2, -4, 1, 3, -2, 3, -1] - Output:
48
Why This Problem is Tricky
Products "flip" when encountering negative numbers:
- A previous max multiplied by a negative number can become a minimum.
- A previous min multiplied by a negative number can become a maximum.
So maintaining just one max is not enough; we must maintain both max_so_far and min_so_far.
Core Idea (One-Pass DP)
When iterating to x = nums[i]:
cur_max: Max product ending ati.cur_min: Min product ending ati.
Transitions:
new_max = max(x, x * cur_max, x * cur_min)new_min = min(x, x * cur_max, x * cur_min)
Global answer is the maximum cur_max seen during traversal.
Complexity
- Time:
O(n) - Space:
O(1)
Python Template
from typing import List
def max_product(nums: List[int]) -> int:
if not nums:
return 0
cur_max = cur_min = ans = nums[0]
for x in nums[1:]:
# Note: new_max/new_min should be based on old values
a = x
b = x * cur_max
c = x * cur_min
new_max = max(a, b, c)
new_min = min(a, b, c)
cur_max, cur_min = new_max, new_min
ans = max(ans, cur_max)
return ans
Common Interview Follow-ups
- How to handle 0? (
max(x, x*...)naturally "restarts" the subarray). - Why maintain min? (Negative number flipping).
- Can we split by 0? (Yes, but DP is cleaner).
If you are preparing for Algorithm VOs at LinkedIn / Meta / Google, oavoservice focuses on training "why define state this way", helping you explain it clearer than you write it.
Need real interview questions? Contact WeChat Coding0201 immediately to get real questions.
联系方式
Email: [email protected] Telegram: @OAVOProxy