कमाल उत्पादन सुबर्रे


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन सिस्को मायक्रोसॉफ्ट मॉर्गन स्टॅन्ले Myntra पीएयू टाइम्स इंटरनेट Zoho
अरे

समस्या विधान

“मॅक्सिमम प्रॉडक्ट सबब्रे” समस्या सांगते की आपल्याला एक दिले गेले आहे अॅरे सकारात्मक आणि positiveणात्मक दोन्ही संख्या असलेल्या पूर्णांकाचे. समस्या विधान उप-अ‍ॅरेचे जास्तीत जास्त उत्पादन शोधण्यास सांगते.

उदाहरण

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 पूर्णांक. आम्ही उप-अ‍ॅरे दिलेल्या अ‍ॅरेमध्ये ठेवलेले जास्तीत जास्त उत्पादन शोधण्यास सांगितले आहे. अ‍ॅरेमध्ये सकारात्मक आणि नकारात्मक दोन्ही आहेत. आम्हाला फक्त येथे जास्तीत जास्त उत्पादन शोधावे लागेल. आपण येथे वापरत असलेला दृष्टिकोन सब-अ‍ॅरेच्या कमाल लांबीइतकीच जास्तीत जास्त बेरीज किंवा कमाल उत्पादनाच्या समान आहे.

आता, आम्ही फक्त सर्व संभाव्य उपनारासह तयार केले जाणारे जास्तीत जास्त उत्पादन यावर लक्ष केंद्रित केले पाहिजे. आमच्याकडे जास्तीत जास्त रेंज आणि मिनिमम रेंजवर लक्ष असेल. मॅक्सव्हॅल्यूमध्ये आम्ही जास्तीत जास्त उत्पादन येथे ठेवणार आहोत. आम्हाला कोणतीही सकारात्मक संख्या सापडली आहे की नाही हे तपासण्यासाठी ध्वज हे व्हेरिएबल आहे आणि 1 शिवाय इतर जास्तीत जास्त उत्पादन देखील उपलब्ध आहे.

आपण अ‍ॅरे 0 ते n पर्यंत नेणार आहोत (जेथे n अ‍ॅरेची लांबी आहे). एर [i] ० पेक्षा जास्त आहे का ते आम्ही तपासू. जर ते सत्य असेल तर मॅक्सिमॅन्ज आणि अरर [i] चे उत्पादन जास्तीत जास्त रेंजमध्ये साठवा. नंतर मिनिमलरेन्ज आणि अरर [i] आणि 0 च्या उत्पादनाच्या दरम्यान किमान मूल्य शोधा आणि ते कमीतकमी रेंजवर साठवा.

यानंतर आणखी एक अट असेल, जर सबरे मधील अ‍ॅरे घटकांपैकी 0 असेल तर किमान रेंज व कमाल रेंज मूल्य 1 वर चिन्हांकित करा. मग आपल्याला येथून पुन्हा सुरु करावे लागेल.

कोणत्याही अटी समाधानी नसल्यास. नंतर मिनिमलरेन्ज आणि अरर [i] मधील उत्पादन दरम्यानचे अधिकतम मूल्य शोधा आणि ते जास्तीत जास्त रेंजवर संचयित करा. कमाल रेंज आणि अररचे उत्पादन [i] किमान रेंजमध्ये संग्रहित केले जातील. प्रत्येक ट्रॅव्हर्व्हलवर, आम्हाला मोठ्या मूल्याची तुलना करून त्यास मॅक्सव्हॅल्यूमध्ये अद्यतनित करावे लागतील आणि शेवटी परत जास्तीत जास्त मॅक्सव्हॅल्यू ज्यात सर्व संभाव्य उपनगरींचे जास्तीत जास्त उत्पादन असेल.

कमाल उत्पादन सुबर्रे

कोड

कमाल उत्पादन सुबर्रे शोधण्यासाठी सीपीपी कोड

#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) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. कारण आम्ही अ‍ॅरे मधील घटकांवर पळवाट लावली. अल्गोरिदम चालविण्यासाठी एकूण वेळ रेषात्मक आहे.

स्पेस कॉम्प्लेक्सिटी

ओ (1) अतिरिक्त जागेची आवश्यकता नसल्यामुळे. कारण आम्ही प्रत्येक घटकासाठी डेटा संग्रहित केलेला नाही. असे करण्याऐवजी आम्ही सतत जागा वापरली आहे आणि अशा प्रकारे जागेची गुंतागुंत स्थिर आहे.