算法: 最大相邻数乘积152. Maximum Product Subarray
Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
It is guaranteed that the answer will fit in a 32-bit integer.
A subarray is a contiguous subsequence of the array.
Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Constraints:
- 1 <= nums.length <= 2 * 104
- -10 <= nums[i] <= 10
- The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
左右两边指针解法
让我试着对这个解决方案做一些解释。
首先，如果数组中没有零，那么具有最大乘积的子数组必须从第一个元素开始或从最后一个元素结束。因此，最大乘积必须是某个前缀乘积或后缀乘积。因此，在这个解决方案中，我们计算出产品的前缀A和后缀的产品B，并简单地返回最大的A和B。
为什么？这是证据：
假设我们有一个子数组A[i : j]( i != 0, j != n) 并且里面的元素的乘积是P。就拿P > 0例如：如果A[i] > 0或者A[j] > 0，那么很明显，我们应该扩展子阵包括A[i]或A[j]; 如果A[i]和A[j]都是负数，则扩展此子数组以包含两者A[i]并A[j]获得更大的乘积。重复这个过程，最终我们将到达 的开始或结束A。
如果数组中有零怎么办？好吧，我们可以将数组拆分为几个较小的数组。也就是说，当前缀积为 时0，我们从当前元素重新开始计算前缀积。而这正是A[i] *= (A[i - 1]) or 1它的作用。
class Solution {
public int maxProduct(int[] nums) {
int res = nums[0];
int l = 0, r = 0;
int len = nums.length;
for (int i = 0; i < len; i++) {
l = (l == 0 ? 1 : l) * nums[i];
r = (r == 0 ? 1 : r) * nums[len - 1 - i];
res = Math.max(res, Math.max(l, r));
}
return res;
}
}
参考
https://leetcode.com/problems/maximum-product-subarray/discuss/183483/JavaC%2B%2BPython-it-can-be-more-simple
