152. 乘积最大子序列
https://leetcode-cn.com/problems/maximum-product-subarray/
解法一:dp
由于乘法遇到0结果清零,因此主要考虑0的影响
用一维dp数组记录,为节省空间可以直接将A[0...i]
连乘结果存放在A[i]
。若遇到0则清零,A[0...i]
最大乘积为A[i]
此处用or
运算实现过滤(所有非0元素与1or
,结果为其本身,0or
1为1。
对原数组正反两个方向运算一遍,取所有结果中的最大值。
最后更新于