Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

DP Solution:

1. State: f[i][j] represents the product from i to j
2. Function: f[i][j] = f[i-1][j] * nums[i], find max during calculation
3. Initial: f[0][0] = nums[0], max = nums[0]
4. Answer: max
5. Improve: rolling array
6. time: O(n^2)

    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
        int[][] f = new int[2][n];
        f[0][0] = nums[0];
        int max = nums[0];

        for (int i = 1; i < n; ++i) {
            f[i%2][i] = nums[i];
            max = Math.max(max, f[i%2][i]);

            int j = i-1;
            while(j >= 0) {
                f[i%2][j] = nums[i] * f[(i-1)%2][j];
                max = Math.max(max, f[i%2][j]);        
                j--;
            }
        }

        return max;
    }

Normal Solution:

1. 3 variants: max, min, answer. One important condition is contiguous.
2. max: max product at i-1, min: min product at i-1
3. encounter negative number, swap min and max
4. use answer to maintain the maximal product

    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        //state
        int n = nums.length;
        int max = nums[0];
        int min = nums[0];
        int answer = nums[0];

        for (int i = 1; i < n; ++i) {
            if (nums[i] < 0) {
                int temp = max;
                max = min;
                min = temp;
            }

            max = Math.max(nums[i], nums[i]*max);
            min = Math.min(nums[i], nums[i]*min);

            answer = Math.max(answer, max);
        }

        return answer;
    }