LeetCode (C/C++) 152. Maximum Product Subarray

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

---

답지 풀이

풀이의 핵심은 곱셈이라 지금은 작은 값도 저장해 두어야 한다는 점이다.

또한 마지막의 값이 최댓값이라는 게 보장되지 않으니 계산할 때마다 따로 저장해야 한다.

 

앞에서부터 탐색하면서 현재 최댓값, 최솟값을 저장하는 과정을 배열의 끝까지 반복한다.
(최솟값이 음수일때 다른 음수를 만나면 최대가 될 수 있기 때문)

 

kadene 알고리즘을 사용해서 풀라는 힌트를 봤지만, 해당 알고리즘은 덧셈 계산에만 사용할 수 있어 보였다.

응용하면 될 것 같았는데 어떻게 해야할 지 감이 안 와서 결국 답을 봤다.
처음에는 절댓값을 저장해보려 했는데 결국 부호를 제거하면 무조건 값을 증가밖에 

최솟값, 최댓값을 따로 저장한다는 생각 못 했는데 오늘도 하나 배웠다.

---

코드

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxVal = nums[0];

        int subMin, subMax;
        subMin = subMax = nums[0];

        for (int i = 1; i < nums.size(); i++) {
            int mn = subMin, mx = subMax;

            // min, max 값을 따로 저장
            subMin = min(nums[i], min(mx * nums[i], mn * nums[i]));
            subMax = max(nums[i], max(mx * nums[i], mn * nums[i]));

            maxVal = max(maxVal, max(subMax, subMin));
        }
        
        return maxVal;
    }
};