LinkedIn VO 面试真题解析：Maximum Product Subarray 最大乘积子数组

Maximum Product Subarray

Given an integer array nums, find the contiguous subarray within the array that has the largest product, and return the product.

这道题要求在一个整数数组中找出乘积最大的连续子数组。由于数组中可能包含负数和 0，最大值和最小值会在遍历过程中互相转换，因此不能像最大子数组和那样只维护一个状态。常见做法是用动态规划同时维护当前位置结尾的最大乘积和最小乘积：遇到正数时更新方向一致，遇到负数时最大与最小会交换角色，遇到 0 则相当于重新开始。最终答案是遍历过程中出现的最大乘积。