[leetcode #152] Maximum Product Subarray

Problem

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
It is guaranteed that the answer will fit in a 32-bit integer.
A subarray is a contiguous subsequence of the array.
Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:

・ 1 <= nums.length <= 2 * 10⁴
・ -10 <= nums[i] <= 10
・ The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Idea

問題は、すべての数値に最大値を乗じたサブアレイを見つけ、最大値を返すことです.
実際のサブアレイに戻る必要はなく,与えられたパラメータarrayを迂回して最大値を計算するだけでよい.
最初は値が正数か負数かを区別し、条件はこうです.しかし、他の人の解答を見て、私はこの必要が全くないことに気づいた.
まず、インデックスごとに最大値と最小値を格納するdparrayを作成します.最大値と最小値、および返される結果値をそれぞれ最初の要素値に設定します.
arrayでは、要素が正の値か負の値かに応じて、最大値と最小値を設定します.正の値の場合、最大値に要素値を乗じた値は最大値、負の値の場合は最小値に要素値を乗じた値は最小値です.毎回返される値を最大値と比較し、最大値が大きい場合は最大値にします.
ナビゲーションが終了したら、値を返すだけです.

Solution

class Solution {
    public int maxProduct(int[] nums) {
        int[] max = new int[nums.length];
        int[] min = new int[nums.length];

        max[0] = min[0] = nums[0];
        int result = nums[0];

        for(int i=1; i<nums.length; i++){
            if(nums[i]>0){
                max[i]=Math.max(nums[i], max[i-1]*nums[i]);
                min[i]=Math.min(nums[i], min[i-1]*nums[i]);
            }else{
                max[i]=Math.max(nums[i], min[i-1]*nums[i]);
                min[i]=Math.min(nums[i], max[i-1]*nums[i]);
            }

            result = Math.max(result, max[i]);
        }

        return result;
    }
}

Reference

https://leetcode.com/problems/maximum-product-subarray/