152. Maximum Product Subarray(최대 곱셈 하위 열)

152. Maximum Product Subarray(최대 곱셈 하위 열)

Maximum Product Subarray 최대 곱셈 하위 열

제목 링크

제목설명

문제 분석

방법 동적 기획

알고리즘 설명

참조 코드

제목 링크
https://leetcode.com/problems/maximum-product-subarray/description/
제목 설명
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4] , the contiguous subarray [2,3] has the largest product = 6 .
제목 분석
이 문제에서는 음과 음의 곱셈이 플러스인 문제를 주의해야 하기 때문에 2차원수조로 곱셈의 최대치와 최소치를 기록해야 한다.만약 현재 숫자가 플러스라면 곱셈의 곱셈이 더욱 크다.반대로 곱하기 마이너스의 성적은 비교적 클 것이다.
방법: 동적 계획
알고리즘 설명nProducts로 마이너스 곱셈을 기록하고, pProducts로 정곱셈을 기록한다nums, 맞다nums[i]:nums[i]>0:

if (pProducts[i - 1] * nums[i] >= nums[i])
    pProducts[i] = pProducts[i - 1] * nums[i];
else
    pProducts[i] = nums[i];

if (nProducts[i - 1] * nums[i] < nums[i])
    nProducts[i] = nProducts[i - 1] * nums[i];
else
    nProducts[i] = nums[i];

 
nums[i] < 0:

if (nProducts[i - 1] * nums[i] >= nums[i])
    pProducts[i] = nProducts[i - 1] * nums[i];
else
    pProducts[i] = nums[i];

if (pProducts[i - 1] * nums[i] < nums[i])
    nProducts[i] = pProducts[i - 1] * nums[i];
else
    nProducts[i] = nums[i];

 
nums[i] == 0:

pProducts[i] = nProducts[i] = 0;

참조 코드

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector<int> pProducts(nums.size(), 1), nProducts(nums.size(), 1);
        pProducts[0] = nProducts[0] = nums[0];
        int max = pProducts[0];
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > 0) {
                if (pProducts[i - 1] * nums[i] >= nums[i])
                    pProducts[i] = pProducts[i - 1] * nums[i];
                else
                    pProducts[i] = nums[i];

                if (nProducts[i - 1] * nums[i] < nums[i])
                    nProducts[i] = nProducts[i - 1] * nums[i];
                else
                    nProducts[i] = nums[i];
            }
            else if (nums[i] < 0) {
                if (nProducts[i - 1] * nums[i] >= nums[i])
                    pProducts[i] = nProducts[i - 1] * nums[i];
                else
                    pProducts[i] = nums[i];

                if (pProducts[i - 1] * nums[i] < nums[i])
                    nProducts[i] = pProducts[i - 1] * nums[i];
                else
                    nProducts[i] = nums[i];
            }
            else {
                pProducts[i] = nProducts[i] = 0;
            }

            if (pProducts[i] > max)
                max = pProducts[i];
        }
        return max;
    }
};