152. 乘积最大子数组

题意：

解题思路：

思路：
1. 依次遍历数组计算当前最大值，不断更新当前最大值；
2. 求出每一步的最大，imax = max(imax * nums[i], nums[i])；
3. 由于存在负数，如果一个正整数乘以一个负数，那会导致这个正整数变成一个负数，因此需要维护一个最小值，imin = min(imin * nums[i], nums[i])
4. 当负数出现时，则用imax与imin交换再进行计算

PHP代码实现：

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function maxProduct($nums) {
        $max = PHP_INT_MIN;
        $imin = $imax = 1;
        foreach ($nums as $num) {
            if ($num < 0) {
                $temp = $imin;
                $imin = $imax;
                $imax = $temp;
            }
            $imin = min($num, $imin * $num);
            $imax = max($num, $imax * $num);
            $max = max($max, $imax);
        }
        return $max;
    }
    function maxProductDp($nums) {
        $dpMax[0] = $dpMin[0] = $nums[0];
        $max = $nums[0];
        for ($i = 1; $i < count($nums); $i++) {
            $dpMax[$i] = max($nums[$i], $dpMax[$i - 1] * $nums[$i], $dpMin[$i - 1] * $nums[$i]);
            $dpMin[$i] = min($nums[$i], $dpMax[$i - 1] * $nums[$i], $dpMin[$i - 1] * $nums[$i]);
            $max = max($max, $dpMax[$i]);
        }
        return $max;
    }
}

GO代码实现：

func maxProduct(nums []int) int {
    imax, imin, ans := nums[0], nums[0], nums[0]
    for i := 1; i < len(nums); i++ {
        mx, mn := imax, imin
        imax = max(mx * nums[i], max(nums[i], mn * nums[i]))
        imin = min(mn * nums[i], min(nums[i], mx * nums[i]))
        ans = max(imax, ans)
    }
    return ans
}
func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}
func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}