[LeetCode#152] Maximum Product Subarray

 

❐ Description

---

문제 링크	https://leetcode.com/problems/maximum-product-subarray/description/
난이도	Medium

 

 

 

 

 

 

❐ 문제 분석

---

이 문제는 배열 내 음수, 0, 양수의 특성을 고려해야 하기 때문에 단순히 한 번의 반복으로 최대값을

찾을 수 없다. 대신 DP를 사용하여 최대값과 최소값을 동시에 추적하여 풀이해야 한다.

 

그럼 왜 최소값도 추적해야 할까? 음수가 곱해질 경우, 최소값이 최대값으로 변할 수 있기 때문이다.

예를들어, `[-2, 3, -4]`에서는

• `-2`를 시작으로 음수를 만나면 곱셈 결과가 양수가 된다.
• 따라서 현재 최소값을 함께 고려해야 최대값을 얻을 수 있다.

 

 

 

 

 

❐ 문제 풀이

---

1. Dynamic Programming

public class SolutionV1 {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        // 초기값 설정
        int maxProduct = nums[0];
        int minProduct = nums[0];
        int result = nums[0];

        // 배열 순회
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];

            // 음수를 만나면 max와 min을 스왑
            if (num < 0) {
                int temp = maxProduct;
                maxProduct = minProduct;
                minProduct = temp;
            }

            // 현재 숫자를 포함한 최대/최소값 갱신
            maxProduct = Math.max(num, maxProduct * num);
            minProduct = Math.min(num, minProduct * num);

            // 최대값 갱신
            result = Math.max(result, maxProduct);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {-3, 0, 1, -2};

        SolutionV1 solution = new SolutionV1();
        int answer = solution.maxProduct(nums);
        System.out.println(answer);
    }
}

 

 

2. Two Pointer

public class SolutionV2 {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int left = 1, right = 1;
        int ans = nums[0];

        for (int i = 0; i < n; i++) {

            //if any of l or r become 0 then update it to 1
            left = left == 0 ? 1 : left;
            right = right == 0 ? 1 : right;

            left *= nums[i];   //prefix product
            right *= nums[n - 1 - i];    //suffix product

            ans = Math.max(ans, Math.max(left, right));

        }

        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {-3, 0, 1, -2};

        SolutionV2 solution = new SolutionV2();
        int answer = solution.maxProduct(nums);
        System.out.println(answer);
    }
}

이 방식의 핵심은 left 또는 right의 값이 0이 될 때 이를 1로 치환하는 것이다.

이렇게 되면 배열 중간에 0이 있는 경우도 대응할 수 있다.

 

위 코드의 동작 방식은 아래와 같다. (leetcode solution paper)

int[] nums = {-3, 0, 1, -2};

// i = 0 / left = 1 / right = 1 / ans = -3
int left = 1 * -3 = -3;
int right = -2 * 1 = -2;
int ans = Math.max(-3, -2) = -2;

// i = 1 / left = -3 / right = -2 / ans = -2
int left = -3 * 0 = 0;
int right = -2 * 1 = -2;
int ans = Math.max(0, -2) = 0;

// i = 2 / left = 0 / right = -2 / ans = 0
int left = 1(left가 0이라면 1로 치환) * 1 = 1; 
int right = -2 * 0 = 0;
int ans = Math.max(0, 1) = 1;

// i = 3 / left = 1 / right = 0 / ans = 1
int left = 1 * -2 = -2;
int right = 1 * -3 = -3;
int ans = Math.max(1, -2) = 1;

 

 

 

 

 

---