TikTok 面试真题解析：最大乘积子数组（Maximum Product Subarray）｜负数翻转核心思维

Problem: Maximum Product Subarray

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product, and return the product.

Example:Input:
nums = [2,3,-2,4]Output:
6Explanation:
The subarray [2,3] has the largest product 6.

Constraints:
1 <= nums.length <= 2 * 10^4
-10 <= nums[i] <= 10
The product of any prefix or suffix of nums fits in a 32-bit integer.

这道题和最大子数组和很像，但因为是“乘积”，情况更复杂。负数会导致符号翻转，因此在遍历时不仅要维护当前的最大乘积，还要维护当前的最小乘积——因为最小值乘以一个负数可能变成新的最大值。通过同时跟踪这两个状态并不断更新全局最大值，就能在线性时间内得到答案。