최대 제품 하위 배열

난이도 중급
자주 묻는 질문 아마존 시스코 Microsoft 모건 스탠리 (Morgan Stanley) 미트라 알레그로 타임즈 인터넷 조호 (Zoho)
배열조회수 62

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

"최대 제품 하위 배열"문제는 사용자에게 정렬 양수와 음수를 모두 포함하는 정수입니다. 문제 설명은 하위 배열의 최대 제품을 찾을 것을 요청합니다.

arr[] = { 2, -2, 3, 5}
15

설명

하위 배열의 요소는 가능한 모든 하위 배열의 최대 곱을 보유하는 3과 5입니다.

암호알고리즘

1. Traverse the array from i = 0 to less than the value n(length of the given array).
  1. Check if arr[i] is greater than 0, if true
    1. Find out the maximumRange by multiplying each value of an array to itself.
    2. Find out the minimumRange between the product of minimumRange and arr[i] and 1.
    3. Mark flag is equal to 1.
  2. If the value of the array is equal to 0, then mark the minimum and maximum range to 1.
  3. Else find out the maximum between the product of minimumRange and arr[i] and 1 and find out the minimumRange by the product value of maximumRange and arr[i].
  4. If maxValue is less than the value of the maximumRange then store the value of maximumRange to maxValue.’
2. Check if the flag is equal to 0 and also maxValue is equal to 1, then return 0
3. Return maxValue.

설명

우리는 정렬 of 정수. 주어진 어레이에서 서브 어레이가 보유 할 수있는 최대 제품을 찾아달라고 요청했습니다. 배열에는 양수와 음수가 모두 포함됩니다. 여기서 최대 제품을 찾아야합니다. 여기서 사용하는 접근 방식은 최대 합계 또는 최대 제품인 하위 배열의 최대 길이와 동일합니다.

이제 가능한 모든 서브 어레이로 만들 수있는 최대 제품에 집중해야합니다. maximumRange와 minimumRange를 살펴 보겠습니다. maxValue에서는 여기에 최대 제품을 저장합니다. 플래그는 양수를 찾았는지 확인하고 1 이외의 최대 제품이 있는지 확인하는 변수입니다.

배열을 0에서 n까지 순회 할 것입니다 (여기서 n은 배열의 길이입니다). arr [i]가 0보다 큰지 확인합니다. 참이면 maximumRange와 arr [i]의 곱을 maximumRange에 저장합니다. 그런 다음 minimumRange와 arr [i]의 곱과 1 사이의 최소값을 찾아 minimumRange에 저장합니다.

그 후 다른 조건이있을 것입니다. 만약 서브 배열의 배열 요소가 0이면 minimumRange와 maximumRange 값을 1로 표시하십시오. 그런 다음 여기서 다시 시작하면됩니다.

조건이 충족되지 않는 경우. 그런 다음 minimumRange의 곱과 arr [i] 사이의 최대 값을 찾아서 maximumRange에 저장합니다. maximumRange와 arr [i]의 곱은 minimumRange에 저장됩니다. 각 순회에서 더 큰 값을 비교하고 maxValue에서 업데이트하고 마지막에 가능한 모든 하위 배열의 최대 제품을 보유 할 maxValue를 반환해야합니다.

최대 제품 하위 배열

암호

최대 제품 하위 배열을 찾는 CPP 코드

#include<iostream>

using namespace std;

int maxSubarrayProduct(int arr[], int n)
{
    int maximumRange = 1;
    int minimumRange = 1;

    int maxValue = 1;
    int flag = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > 0)
        {
            maximumRange = maximumRange * arr[i];
            minimumRange = min(minimumRange * arr[i], 1);
            flag = 1;
        }
        else if (arr[i] == 0)
        {
            maximumRange = 1;
            minimumRange = 1;
        }
        else
        {
            int temp = maximumRange;
            maximumRange = max(minimumRange * arr[i], 1);
            minimumRange = temp * arr[i];
        }
        if (maxValue < maximumRange)
            maxValue = maximumRange;
    }
    if (flag == 0 && maxValue == 1)
        return 0;
    return maxValue;
}
int main()
{
    int arr[] = { 2,-2,-3,-5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum Sub array product is "<< maxSubarrayProduct(arr, n);
    return 0;
}
Maximum Sub array product is 15

최대 제품 하위 배열을 찾는 Java 코드

class productSubarray
{
    public static int maxSubarrayProduct(int arr[])
    {
        int n = arr.length;
        int maximumRange = 1;
        int minimumRange = 1;

        int maxValue = 1;
        int flag = 0;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] > 0)
            {
                maximumRange = maximumRange * arr[i];
                minimumRange = Math.min(minimumRange * arr[i], 1);
                flag = 1;
            }
            else if (arr[i] == 0)
            {
                maximumRange = 1;
                minimumRange = 1;
            }
            else
            {
                int temp = maximumRange;
                maximumRange = Math.max(minimumRange * arr[i], 1);
                minimumRange = temp * arr[i];
            }
            if (maxValue < maximumRange)
                maxValue = maximumRange;
        }
        if (flag == 0 && maxValue == 1)
            return 0;
        return maxValue;
    }
    public static void main(String[] args)
    {
        int arr[] = { 2,-2,-3,-5};
        System.out.println("Maximum Sub array product is "+ maxSubarrayProduct(arr));
    }
}
Maximum Sub array product is 15

복잡성 분석

시간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 배열의 요소에 대해 루프를 실행했기 때문입니다. 알고리즘을 실행하는 데 걸리는 총 시간은 선형입니다.

공간 복잡성

O (1) 추가 공간이 필요하지 않습니다. 각 요소에 대한 데이터를 저장하지 않았기 때문입니다. 그 대신 우리는 일정한 공간을 사용했기 때문에 공간의 복잡성은 일정합니다.

균열 시스템 설계 인터뷰
Translate »