[LeetCode] 152. Maximum Product Subarray 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Maximum Product Subarray

---

문제 요약 (Maximum Product Subarray)

정수 배열이 주어질 때, 연속된 부분 배열(subarray) 중에서 곱이 가장 큰 값을 구하라.

문제링크: https://leetcode.com/problems/maximum-product-subarray

---

🤔 처음 떠올린 아이디어

처음에는 이렇게 생각했다.

그냥 계속 곱해가면서 최대값을 갱신하면 되지 않을까?

Kadane처럼 현재까지의 곱을 유지하면서
최대값을 업데이트하면 될 것 같았다.

하지만 바로 이런 예시에서 깨졌다.

[2, 3, -2, 4]

2 × 3 = 6
6 × -2 = -12

여기서 갑자기 음수 때문에 값이 망가진다.
그리고 더 치명적인 예시가 있다.

[-2, 3, -4]

-2 × 3 = -6
-6 × -4 = 24

중간에 -6은 “나쁜 값”처럼 보였지만
다음 음수를 만나자 갑자기 최댓값이 되었다.

여기서 관점이 바뀌었다.

---

💡 핵심 깨달음: 최소값이 미래의 최대값이 된다

곱셈은 덧셈과 다르다.

음수를 곱하는 순간
최대값과 최소값의 역할이 뒤집힌다.

• max × (-) → min
• min × (-) → max

즉,

지금은 최소처럼 보이는 값도
미래에는 최대가 될 수 있다.

그래서 이 문제는
“최대값 하나만” 들고 가면 절대 안 된다.

항상 동시에 관리해야 할 것:

• 현재 위치까지의 최대값
• 현재 위치까지의 최소값

---

🧠 매 단계에서 무엇을 비교해야 할까?

현재 숫자를 num이라고 하자.
우리가 만들 수 있는 후보는 세 가지다.

• 1️⃣ num 혼자 시작
• 2️⃣ num × 이전 최대값
• 3️⃣ num × 이전 최소값

그래서 점화식은 이렇게 된다.

newMax = max(num, num * prevMax, num * prevMin)
newMin = min(num, num * prevMax, num * prevMin)

그리고 global max를 갱신한다.

---

🔁 음수면 swap 해도 되는 이유

음수를 만나면 이런 일이 벌어진다.

• max × (-) → 최소
• min × (-) → 최대

즉, max와 min의 역할이 바뀐다.
그래서 이렇게 정리할 수 있다.

1. 음수면 max/min을 swap
2. 그 다음 일반 로직 적용

---

코드 (Java)

class Solution {
    public int maxProduct(int[] nums) {
        int maxVal = nums[0];
        int minVal = nums[0];
        int result = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];

            if (num < 0) {
                int temp = maxVal;
                maxVal = minVal;
                minVal = temp;
            }

            maxVal = Math.max(num, maxVal * num);
            minVal = Math.min(num, minVal * num);

            result = Math.max(result, maxVal);
        }

        return result;
    }
}

0이 등장하면 어떻게 될까?
0을 만나면 곱은 강제로 끊긴다.
[2, 3, 0, -2, -3]
0 이후는 새로 시작해야 한다.

위 로직에서는 자연스럽게 처리된다.

maxVal = max(num, maxVal * num)

num이 0이면
maxVal은 자동으로 0이 되고
다음 숫자에서 다시 시작하게 된다.

📈 시간 / 공간 복잡도

• 시간: 배열 한 번 순회 → O(N)
• 공간: 변수 3개만 사용 → O(1)

---

📝 이번 문제에서 얻은 깨달음

• 곱셈 문제는 부호 때문에 상태가 뒤집힌다.
• “최대값만 추적”하는 사고는 덧셈 문제에서만 통한다.
• 최소값은 잠재적 최대값이다.
• 음수는 위기이자 기회다.

👉 결국 중요한 건

“곱은 방향이 뒤집히는 연산”이라는 것을 이해하는 것이었다!