[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.

The test cases are generated so 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^4
• -10 <= nums[i] <= 10
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

---

Solution

class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0];
        int left = 0;
        int right = 0;
        for (int i = 0; i < nums.length; i++) {
            left = (left == 0 ? 1 : left) * nums[i];
            right = (right == 0 ? 1 : right) * nums[nums.length - 1 - i];
            max = Math.max(max, Math.max(left, right));
        }
        return max;
    }
}

Explanation

• 배열속 전체 요소들의 곱을 구하기 위해서는, 배열의 첫 요소와 다음 요소를 곱해 나온 값에 다음 요소를 곱하는 방식을 반복하면 된다.
• 곱의 최대값을 나타내는 변수 max에 배열의 첫 요소를 할당하고, 곱셈 값을 할당하기 위한 변수 left를 선언한다. 그리고 for 반복문을 통해 배열의 첫 요소부터 시작해 곱셈을 시작한다.
• 배열의 요소에 0이 있는 경우는 해당 요소 이후의 곱셈을 진행하는 의미가 없기 때문에, 다음 요소부터 다시 곱셈을 진행할 수 있도록 for 반복문 속에 조건문을 작성한다.

  int max = nums[0];
  int left = 0;
  for (int i = 0; i < nums.length; i++) {
    left = (left == 0 ? 1 : left) * nums[i];
    max = Math.max(max, left);
  }
  

• 배열의 첫 요소부터 곱셈을 진행하게 되면 모든 경우의 수를 계산할 수 없으므로, 배열의 마지막 요소부터 진행하는 곱셈을 추가한다.

  int max = nums[0];
  int left = 0;
  int right = 0;
  for (int i = 0; i < nums.length; i++) {
    left = (left == 0 ? 1 : left) * nums[i];
    right = (right == 0 ? 1 : right) * nums[nums.length - 1 - i];
    max = Math.max(max, Math.max(left, right));
  }
  

• 계산된 최대값을 나타내는 변수 max를 반환한다.

  return max;