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,结果为其本身,0or1为1。

对原数组正反两个方向运算一遍,取所有结果中的最大值。

class Solution:
    def maxProduct(self, A: List[int]) -> int:
        B = A[::-1]  #反向运算
        #在一次遍历中完成正反
        for i in range(1, len(A)):
            A[i] *= A[i - 1] or 1
            B[i] *= B[i - 1] or 1
        return max(max(A),max(B)) 

最后更新于