LeetCode - Maximum Product Subarray

문제 설명

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.

제약사항

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

Solution

1. Brute force

• 이중 for문을 순회하면서 i ~ j 까지의 subarray 곱을 구함
• O(n^2)

import java.util.*;

class Solution {
    public int maxProduct(int[] nums) {

        int maxProd = nums[0];

        for (int i = 0; i < nums.length; i++) {
            int preProd = 1;
            for (int j = i; j < nums.length; j++) {
                if (i == j) {
                    preProd = nums[j];
                } else {
                    preProd = preProd * nums[j];
                }
                maxProd = Math.max(maxProd, preProd);
            }
        }
        return maxProd;
    }

2. DP

• 주어진 현재값 currVal=0,
  1) maxAccProd, minAccProd 값에 상관없이
  - maxAccProd=0
  - minAccProd=0
• 주어진 현재값 currVal>0,
  1) maxAccProd>0, minAccProd>0 이면,
  - maxAccProd= maxAccProdcurrVal
  - minAccProd=currVal
  2) maxAccProd>0, minAccProd<0 이면,
  - maxAccProd= maxAccProdcurrVal
  - minAccProd=minAccProd*currVal
  ...

public int maxProductWithDP(int[] nums) {
        if (nums.length == 0)
            return 0;

        int maxAccProd=nums[0]; // 부분 최대곱 저장 변수
        int minAccProd = maxAccProd; // 부분 최소곱 저장 변수
        int maxProd = maxAccProd; // 갱신 되는 최대곱 저장 변수

        for (int i = 1; i < nums.length; i++) {
            
            int currVal = nums[i]; // i번째 값

	    // 현재값, 부분최대곱x현재값, 부분최소곱x현재값을 비교하여 부분최대곱 갱신
            int tempMax= Math.max(maxAccProd * currVal, Math.max(minAccProd * currVal, currVal));
            // 현재값, 부분최대곱x현재값, 부분최소곱x현재값을 비교하여 부분최소곱 갱신
            minAccProd = Math.min(maxAccProd * currVal, Math.min(minAccProd * currVal, currVal));
            maxAccProd = tempMax;
	   // 최대곱 갱신
            maxProd = Math.max(maxAccProd, maxProd);

        }
    }