Leetcode152——Maximum Product Subarray

作者:Tyan博客:noahsnail.com  |  CSDN  | 

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 Subarayと似ていて、三重サイクル、二つのサイクルで解決できます.しかし,動的計画で解決し,状態遷移方程式を見つけることが最も重要である.積は負であり、負は正である可能性があるため、i-1回目の積最大値(maxValue Pre)と最小値(minValue Pre)の両方を保持する必要がある.もちろん、最大値最小値配列を定義して、i回目の積の最大値(maxValue)と最小値(minValue)を保存することもできます.Maximum Subarayと比較して、最大値は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;
    }
}