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