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


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना सिस्को माइक्रोसॉफ्ट मॉर्गन स्टेनली Myntra 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 पूर्णांक। हमने अधिकतम उत्पाद खोजने के लिए कहा है जो किसी दिए गए सरणी में उप-सरणी रख सकता है। सरणी में धनात्मक और ऋणात्मक दोनों संख्याएँ होती हैं। हमें बस यहां अधिकतम उत्पाद ढूंढना है। हम यहां जिस दृष्टिकोण का उपयोग कर रहे हैं, वह उप-सरणी की अधिकतम लंबाई या अधिकतम उत्पाद के समान है।

अब, हमें बस अब उस अधिकतम उत्पाद पर ध्यान केंद्रित करना होगा जो सभी संभावित उप-चरणों के साथ बनाया जा सकता है। हम अधिकतम और न्यूनतम राशि पर नजर रखेंगे। मैक्सवेल में, हम यहां अधिकतम उत्पाद को स्टोर करने जा रहे हैं। ध्वज यह जाँचने का चर है कि क्या हमें कोई सकारात्मक संख्या मिली है और साथ ही 1 से अधिक अधिकतम उत्पाद मौजूद है।

हम एरे को 0 से n तक ले जा रहे हैं (जहाँ n एरे की लंबाई है)। हम जाँच करेंगे कि क्या गिरफ्तारी [i] ० से अधिक है। यदि यह सत्य है, तो अधिकतमरंगे और गिरफ्तारी के उत्पाद को जमा करें [i]। फिर मिनिमंगे और गिरफ्तारी [i] और 0 के उत्पाद के बीच न्यूनतम मूल्य का पता लगाएं, और इसे मिनिममेंज पर स्टोर करें।

उसके बाद एक और शर्त होगी, अगर सबर्रे में कोई भी एलीमेंट तत्व 0 है, तो मिनिममंगे और मैक्सिमारेंज वैल्यू को 1. पर मार्क करें। फिर हमें यहां से रीस्टार्ट करना है।

यदि कोई भी स्थिति संतुष्ट नहीं है। फिर मिनिमंगे और गिरफ्तारी [i] के उत्पाद के बीच अधिकतम मूल्य का पता लगाएं और इसे अधिकतम रेंजर पर संग्रहीत करें। अधिकतमरेंज और गिरफ्तारी [i] के उत्पाद को न्यूनतमरेंज में संग्रहीत किया जाएगा। प्रत्येक ट्रैवर्सल पर, हमें अधिक से अधिक मूल्य की तुलना करनी होगी और इसे मैक्सवैल्यू में अपडेट करना होगा और आखिरी में मैक्सवेल को वापस करना होगा जो सभी संभावित सबरेज का अधिकतम उत्पाद धारण करेगा।

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

कोड

अधिकतम उत्पाद सबर्रे खोजने के लिए 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

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

समय जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है। क्योंकि हम सरणी में तत्वों पर एक लूप चलाते थे। एल्गोरिथ्म को चलाने के लिए लिया गया कुल समय रैखिक है।

अंतरिक्ष जटिलता

ओ (1) के रूप में कोई अतिरिक्त स्थान की आवश्यकता है। क्योंकि हमने प्रत्येक तत्व के लिए डेटा संग्रहीत नहीं किया है। ऐसा करने के बजाय हमने निरंतर स्थान का उपयोग किया है और इस प्रकार अंतरिक्ष जटिलता निरंतर है।