Maximum Product Subarray

Category: Array

Deadline: 1st week (12/31 - 1/7)

Difficulty: Medium

Github: https://github.com/iamseokhyun/2022-algorithm-study/tree/master/array/MaximumProductSubarray/

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

Problem

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: nums = [2,3,-2,4]

Output: 6

Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]

Output: 0

Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:

1 <= nums.length <= 2 * 10^4
-10 <= nums[i] <= 10
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Solution

public class Solution
{
    public int MaxProduct(int[] nums)
    {
        int istrt = 0;
        int tmp = 0;
        bool isStarted = false;
        int max = nums[0];
        bool isZero = false;

        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] == 0)
            {
                isZero = true;

                if (isStarted)
                {
                    tmp = NoZeroMax(nums[istrt..i]);
                    if (tmp > max)
                    {
                        max = tmp;
                    }
                    isStarted = false;
                }
            }
            else
            {
                if (!isStarted)
                {
                    isStarted = true;
                    istrt = i;
                }
            }
        }

        if (isStarted)
        {
            tmp = NoZeroMax(nums[istrt..nums.Length]);
            if (tmp > max)
            {
                max = tmp;
            }
        }

        if (isZero)
        {
            if (max < 0)
            {
                return 0;
            }
        }

        return max;
    }

    public int NoZeroMax(int[] nums)
    {
        if (nums.Length == 1)
        {
            return nums[0];
        }
        else
        {
            int minuscnt = 0;
            int idx1 = -1;
            int idx2 = -1;

            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] < 0)
                {
                    if (idx1 == -1)
                    {
                        idx1 = i;
                    }
                    minuscnt++;
                    idx2 = i;
                }
            }

            if ((minuscnt % 2) == 0)
            {
                int prod = 1;
                for (int i = 0; i < nums.Length; i++)
                {
                    prod *= nums[i];
                }
                return prod;
            }
            else
            {
                int prod = 1;
                for (int i = 0; i < nums.Length; i++)
                {
                    prod *= nums[i];
                }

                int byprod1 = 1;
                for (int i = 0; i <= idx1; i++)
                {
                    byprod1 *= nums[i];
                }

                int byprod2 = 1;
                for (int i = idx2; i < nums.Length; i++)
                {
                    byprod2 *= nums[i];
                }

                if (byprod1 > byprod2)
                {
                    return prod / byprod1;
                }
                else
                {
                    return prod / byprod2;
                }
            }
        }
    }
}

Comment

MaxProduct : NoZeroMax에 넣기 위해 nums 사이의 0을 기준으로 array를 분할한다. NoZeroMax : array 전체에 0이 들어있지 않음이 보장된(MaxProduct에 의해) input이 들어올 때 Subarray Product의 최대를 구함.
0을 제외한 정수의 절댓값은 항상 1보다 크므로 수의 절댓값은 곱함에 따라 점차 커짐. 부호가 양수일 경우 array 전체를 곱한 수가 최대이며, 음수일 경우 좌측과 우측으로부터 최초의 - 부호를 갖는 숫자를 하나 제외하고 곱한 값중 큰 쪽이 최대이므로 이를 계산.
MaxProduct로 전체 nums를 잘게 쪼개고, NoZeroMax에 쪼갠 array 투입, NoZeroMax는 곱이 양수일 때 모든수의 곱을 출력하며, 음수일 때 좌측 -를 빼는게 나은지 우측 -를 빼는게 나은지를 판단하여 최댓값 출력.

댓글을 불러오는 중입니다.