dp related problems (update continuously)

Leetcode Maximum Product Subarray

这个问题是说给一个整数数组。求最大连续子阵列产品。

纠结了包括阵列中的很长一段时间0而如何处理负数，关键的事实是，负治疗，所以我们录得最大正值和最小负值，这样就能够非常easy的处理负数的情况了。对于当前元素假设是负数，那么最大值可能是前面的最小负值乘以当前的负数；假设是正数，那么则非常有可能是前面的最大正值乘以当前正数。

于是我们记dpp[i]为以第i个数结尾的最大正值。dpn[i]表示以第i个数结尾的最小负值，那么就有以下的两种更新情况：

if A[i] > 0:

dpp[i] = max(A[i], dpp[i-1]*A[i])

dpn[i] = min(0, dpn[i-1]*A[i])

if A[i] < 0:

dpn[i] = min(A[i], A[i]*dpp[i-1])

dpp[i] = max(0, A[i]*dpn[i-1])

而且在遍历的过程中用dpp[i]更新终于的结果值即可了。详细可參考以下的代码。

class Solution:
    # @param A, a list of integers
    # @return an integer
    def maxProduct(self, A):
        if A == None:
            return 0
        if len(A) == 0:
            return 0
        if len(A) == 1:
            return A[0]
        
        dpp = [0]*len(A)
        dpn = [0]*len(A)
        
        ans = A[0]
        if A[0] > 0 :
            dpp[0] = A[0]
        elif A[0] < 0 :
            dpn[0] = A[0]
            
        for i in range(1, len(A)):
            if A[i] == 0 :
                continue
            elif A[i] > 0 : 
                dpp[i] = max(A[i], A[i]*dpp[i-1])
                dpn[i] = min(0, A[i]*dpn[i-1])
            else:
                dpn[i] = min(A[i], A[i]*dpp[i-1])
                dpp[i] = max(0, A[i]*dpn[i-1])
            ans = max(dpp[i], ans)
        return ans