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

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

---

풀이

전에 답지를 보고 풀었던 문제라 그 기억으로 풀어보았다.

 

해당 문제는 곱한 값을 구하는 문제로, 현재는 작은 값들도 저장하고 있어야 하므로,

subMax, subMin의 값으로 현재 최댓값, 최솟값을 따로 저장해두었다.

이를 구할 때는 이전 합 * 현재 값을 비교하여 저장한다. (최솟값 * 음수일 경우 해당 값이 최대가 되므로)

또한 이와 현재 값을 비교해 저장해야 subarray가 이어질 수 있다.

이를 주어진 배열의 끝까지 순회하며 maxProduct를 구한다.

---

코드

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int subMax = 1, subMin = 1;
        int ans = -100;

        for (int n : nums) {
            int mx = subMax, mn = subMin;
            subMax = max(n, max(mx * n, mn * n));
            subMin = min(n, min(mx * n, mn * n));

            ans = max(ans, subMax);
        }
        return ans;
    }
};