(Array, Medium) Maximum Product Subarray

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

이 문제는 기본적으로 maximum subarray와 같아 보이지만 굉장히 다르다.

곱셈의 특성 때문이다.

음수와 양수의 곱은 음수가 되기 때문에 다음 숫자에 따라 더 커질 수도,
작아질 수도 있기 때문이다.

그래서 단순히 누계가 0(혹은 현재 인덱스 값)보다 작은 경우 누계를 버리고 새로 쌓는다는 maximum subarray 문제의 아이디어는 적합하지 않은 것이다.

이 문제를 해결하기 위해서는 현재 값을 기반으로 양수/음수 가능성을 모두 추적해야 한다.
그러므로 min, max 관리할 변수가 필요하며 이것을 기반으로 계산해주어야 한다.

주의해야 할 점은 아래 세 가지 케이스 중에 어떤 것이 가장 큰(혹은 가장 작은)값인지 확실하게 해야한다는 점이다.

1. nums[i] 그 자체
2. max 누계 * nums[i]
3. min 누계 * nums[i]

곱셈이기 때문에 어느 케이스가 가장 적합할지는 모두 계산을 해봐야 알기 때문이다.
각 케이스마다 세 갈래의 길이 있다고 이해하면 좋다.

가장 작은 값에 현재 값을 곱하는 것이 가장 크냐/작냐?
가장 큰 값에 현재 값을 곱하는 것이 가장 크냐/작냐?
아니면 누계를 버릴까? == 현재 값이 가장 크냐 / 쟉냐? --> 서브어레이를 해당 아이템에서 자르는 행위라고 볼 수 있겠다.

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

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

        int answer = nums[0];

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

            // max에 v곱한것이 제일 클 수도, min에 v곱한것이 제일 클 수도, 혹은 v자체가 제일 클 수도 있다.
            max = Math.max(Math.max(max * v, min * v), v);
            // 마찬가지로 세 경우에서 가장 작은 값을 찾는다.
            min = Math.min(Math.min(maxCopy * v, min * v), v);

            answer = Math.max(answer, max);
        }

        return answer;
    }
}