152. Maximum Product Subarray

Version #1 Optimized DP
是一个dp题，对于乘法来说情况比较特殊，因为有负数
如果一个绝对值非常大的负数再乘一个负数，负负得正，有产生最大值的可能
所以要同时keep track of dpMin 以及dpMax
更新dp的时候要考虑也可是nums[i] 单独成为最大或者最小


70.82 %
class Solution {
    public int maxProduct(int[] nums) {
        // pos[i] -> maxProduct ends with current nums[i]
        // neg[i] -> minProduct ends with current nums[i]
        // pos[i] = Math.max(nums[i], Math.max(post[i - 1] * nums[i], neg[i - 1] * nums[i]));
        // neg[i] = Math.min(nums[i], Math.min(post[i - 1] * nums[i], neg[i - 1] * nums[i]));
        int result = Integer.MIN_VALUE;
        int pos = 1, neg = 1;
        for (int i = 0; i < nums.length; i++) {
            int currPos = Math.max(nums[i], Math.max(pos * nums[i], neg * nums[i]));
            int currNeg = Math.min(nums[i], Math.min(pos * nums[i], neg * nums[i]));
            pos = currPos;
            neg = currNeg;
            result = Math.max(pos, result);
        }
        return result;
    }
}