、Maximum Product Subarray

1. 問題描述

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

For example, given the array [2,3,-2,4],

the contiguous subarray [2,3] has the largest product = 6.

2. 求解

這個題跟Leetcode 53——Maximum Subarray類似，可以用三重循環，兩種循環解決。但最好的還是用動态規劃解決，找出狀态轉移方程最關鍵。由于乘積可能為負數，負負得正，是以第

i-1

次的乘積最大值（maxValuePre）與最小值（minValuePre）都需要保留。當然也可以定義最大值最小值數組來儲存第i次乘積的最大值（maxValue）與最小值（minValue）。與Maximum Subarray相比，最大值為

maxValue = max(minValuePre * nums[i], maxValuePre * nums[i], nums[i])

，最小值同樣如此。

沒有定義最大值數組與最小值數組

public class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int maxValue = nums[0];
        int minValue = nums[0];
        int result = nums[0];
        int maxValuePre = nums[0], minValuePre = nums[0];
        for(int i = 1; i < n; i++) {
            maxValue = Math.max(minValuePre * nums[i], Math.max(maxValuePre * nums[i], nums[i]));
            minValue = Math.min(minValuePre * nums[i], Math.min(maxValuePre * nums[i], nums[i]));
            if(maxValue > result) {
                result = maxValue;
            }
            maxValuePre = maxValue;
            minValuePre = minValue;
        }
        return result;
    }
}           

複制

定義最大值數組與最小值數組

public class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int maxValue[] = new int[nums.length];
        int minValue[] = new int[nums.length];
        maxValue[0] = nums[0];
        minValue[0] = nums[0];
        int result = nums[0];
        for(int i = 1; i < n; i++) {
            maxValue[i] = Math.max(minValue[i - 1] * nums[i], Math.max(maxValue[i - 1] * nums[i], nums[i]));
            minValue[i] = Math.min(minValue[i - 1] * nums[i], Math.min(maxValue[i - 1] * nums[i], nums[i]));
            if(maxValue[i] > result) {
                result = maxValue[i];
            }
        }
        return result;
    }
}           

複制