زیر مجموعه حداکثر محصول


سطح دشواری متوسط
اغلب در آمازون سیسکو مایکروسافت مورگان استنلی میندا PayU بار اینترنت ZOHO
صف

بیان مسأله

مسئله "حداکثر زیرشکل محصول" بیان می کند که به شما یک عدد داده می شود صف عدد صحیح حاوی اعداد مثبت و منفی است. بیانیه مسئله می خواهد حداکثر محصول زیر آرایه را پیدا کند.

مثال

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 عدد صحیح ما خواسته ایم حداکثر محصولی را که یک زیر آرایه می تواند در آرایه داده شده داشته باشد ، پیدا کنیم. آرایه حاوی هر دو عدد مثبت و منفی است. ما فقط باید حداکثر محصول را در اینجا پیدا کنیم. روشی که ما در اینجا استفاده می کنیم همان حداکثر طول زیر آرایه به عنوان حداکثر مجموع یا حداکثر محصول است.

اکنون ، ما فقط باید روی حداکثر محصولی که می توان با تمام زیرگروه های ممکن تولید کرد ، تمرکز کنیم. ما چشم به حداکثر Range و minimumRange خواهیم داشت. در maxValue ، ما قصد داریم حداکثر محصول را در اینجا ذخیره کنیم. Flag متغیری است برای بررسی اینکه آیا عدد مثبتی پیدا کرده ایم یا نه و همچنین حداکثر محصول غیر از 1 وجود دارد.

ما می خواهیم آرایه را از 0 به n رد کنیم (جایی که n طول آرایه است). بررسی خواهیم کرد که آیا arr [i] بیشتر از 0 است یا خیر. اگر درست است ، محصول MaxRange و arr [i] را در MaxRange ذخیره می کنیم. سپس مقدار حداقل بین محصول minimumRange و arr [i] و 1 را دریابید و آن را در minimumRange ذخیره کنید.

پس از آن یک شرط دیگر وجود خواهد داشت ، اگر هر یک از عناصر آرایه در زیر آرایه 0 باشد ، مقدار minimumRange و maximumRange را به 1 علامت گذاری کنید. سپس ما فقط باید از اینجا دوباره راه اندازی کنیم.

اگر هیچ یک از شرایط برآورده نشود. سپس حداکثر مقدار را بین محصول minimumRange و arr [i] دریابید و آن را در maximumRange ذخیره کنید. محصول حداکثر Range و 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

کد جاوا برای یافتن زیر مجموعه حداکثر محصول

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) جایی که "n" تعداد عناصر آرایه است. زیرا ما یک حلقه را روی عناصر آرایه اجرا کردیم. کل زمان لازم برای اجرای الگوریتم خطی است.

پیچیدگی فضا

O (1) زیرا فضای اضافی مورد نیاز نیست. زیرا ما داده هایی را برای هر عنصر ذخیره نکرده ایم. به جای این کار ما از فضای ثابت استفاده کرده ایم و بنابراین پیچیدگی فضا ثابت است.