अधिकतम उत्पादन सुबर्रे


कठिनाई तह मध्यम
बारम्बार सोधिन्छ अमेजन सिस्को माइक्रोसफ्ट मोर्गन स्टेनले Myntra PayU टाइम्स इन्टरनेट Zoho
एरे

समस्या वक्तव्य

समस्या "अधिकतम उत्पादन सुबर्रे" भन्छ कि तपाईंलाई एक दिइयो array सकारात्मक र नकारात्मक संख्या दुवै भएको पूर्णांकको। समस्या कथनले उप-एर्रेको अधिकतम उत्पादन पत्ता लगाउन सोधेको छ।

उदाहरणका

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

स्पष्टीकरण

सब एरेमा एलिमेन्टहरू and र are हुन् जसले सबै सम्भावित उप-एर्रेको अधिकतम उत्पादन राख्दछ।

अल्गोरिदम

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.

स्पष्टीकरण

हामीले एउटा दिएका छौं array of पूर्णांक हामीले अधिकतम उत्पादन पत्ता लगाएका छौं जुन सब एरेले दिएको एर्रेमा समात्न सक्छ। एर्रेमा दुबै सकारात्मक र नकारात्मक संख्याहरू समावेश छन्। हामीले यहाँ अधिकतम उत्पादन फेला पार्नु पर्छ। दृष्टिकोण हामी यहाँ प्रयोग गर्दै छौं उप-एर्रेमीको अधिकतम लम्बाई बराबर हो अधिकतम योग वा अधिकतम उत्पादनको रूपमा।

अब हामीले केवल अधिकतम उत्पादनमा ध्यान केन्द्रित गर्नुपर्नेछ जुन सबै सम्भव सबार्रेहरूमार्फत बनाउन सकिन्छ। हामीसँग अधिकतम र्यान्ज र न्यूनतम रेंजमा आँखा हुनेछ। अधिकतममा हामी यहाँ अधिकतम उत्पादन भण्डार गर्न गइरहेका छौं। झण्डा चर हो कि जाँच गर्नका लागि यदि हामीले कुनै सकारात्मक नम्बर फेला पारेका छौं र १ भन्दा बाहेक अधिकतम उत्पादन पनि छ भने।

हामी एर्रेलाई ० देखि n सम्म ट्रान्सभर्स गइरहेका छौं (जहाँ n एर्रेको लम्बाई हो)। हामी जाँच गर्दछौं यदि एर [i] ० भन्दा ठूलो छ भने। यदि यो सत्य हो भने, म्याक्समेन्ज र एररको उत्पादन [i] अधिकतम रेंजमा भण्डार गर्नुहोस्। तब न्यूनतम रान्ज र एरर [i] र १ को उत्पादन बीच न्यूनतम मान फेला पार्नुहोस् र यसलाई न्यूनतम रेंजमा भण्डार गर्नुहोस्।

त्यस पछि त्यहाँ अर्को सर्त हुनेछ, यदि सुबर्रेमा कुनै एर्रे एलिमेन्ट्स ० छ, तब न्यूनतम रान्ज र अधिकतम रेंज मान १ मा चिन्ह लगाउनुहोस्। त्यसपछि हामीले यहाँबाट फेरि सुरु गर्नुपर्नेछ।

यदि कुनै पनि शर्तहरु सन्तुष्ट छैन। तब न्यूनतम रान्ज र एररको उत्पादन बीचको अधिकतम मान पत्ता लगाउनुहोस् [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

जटिलता विश्लेषण

समय जटिलता

ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। किनकि हामीले एर्रेमा एलिमेन्टहरू माथि लूप दियौं। एल्गोरिथ्म चलाउनको लागि लिइएको कुल समय रेखीय हो।

ठाउँ जटिलता

O (१) कुनै अतिरिक्त ठाउँको आवश्यक छ। किनकि हामीले प्रत्येक तत्वको लागि डाटा भण्डारण गरेका छैनौं। त्यसो गर्नुको सट्टा हामीले निरन्तर खाली स्थान प्रयोग गर्यौं र यसरी अन्तरिक्ष जटिलता स्थिर हो।