アルゴリズム(LeetCode_152_積最大サブ配列)

アルゴリズム#アルゴリズム#
あらすじ:またダイナミックプランニングとメモリー検索を使った問題で、前回の練習に引き継ぎましょう.出典:力扣(LeetCode)链接:积累最大サブ配列アルゴリズムの考え方前のブログを参照:最低運賃
タイトル
整数配列numsを与えます.配列内の積が最も大きい連続サブ配列(少なくとも1つの数値を含む)を見つけ、サブ配列に対応する積を返します.
例
例1:入力:[2,3,−2,4]出力:6解釈:サブ配列[2,3]に最大積6がある.例2:入力:[-2,0,-1]出力:0解釈:結果は2ではありません.[-2,-1]はサブ配列ではありません.
Javaコード

class Solution {
    int []nums;
    int [][]memo1;
    boolean [][]memo2;
    public int maxProduct(int[] nums) {
        this.nums = nums;
        memo1 = new int [nums.length][2];
        memo2 = new boolean[nums.length][2];
        int a = nums[0];
        for(int i = 1;i<nums.length;i++)
        {
            if(a<imax(i))
            {
                a=imax(i);
            }
        }
        return a;
    }
    public int imin(int i)
    {
        if(i==0)
        {
            return nums[0];
        }
        if(!memo2[i][0])
        {
            memo2[i][0] = true;
            memo1[i][0] = Math.min(Math.min(imin(i-1)*nums[i],imax(i-1)*nums[i]),nums[i]);
        }
        return memo1[i][0];
    }
    public int imax(int i)
    {
        if(i==0)
        {
            return nums[0];
        }
        if(!memo2[i][1])
        {
            memo2[i][1] = true;
            memo1[i][1] = Math.max(Math.max(imin(i-1)*nums[i],imax(i-1)*nums[i]),nums[i]);
        }
        return memo1[i][1];
    }
}