एक गोलाकार सरणी में लगातार अंतर का योग अधिकतम करें  


कठिनाई स्तर आसान
में अक्सर पूछा ताल भारत ईबे जीई हेल्थकेयर खरात Quora एसएपी लैब्स चौकोर
ऐरे लालची छंटाई

समस्या का विवरण  

मान लीजिए कि आपने ए पूर्णांक सरणी। इस सरणी को एक माना जाना चाहिए गोलाकार सरणी। किसी सरणी का अंतिम मान पहले सरणी से जुड़ा होगा, an ⇒ ए १। समस्या "एक गोलाकार सरणी में लगातार अंतर के योग को अधिकतम करें" प्रत्येक लगातार तत्व के बीच अंतर के अधिकतम योग का पता लगाने के लिए कहता है। तो आपको एक निरंतर तत्व के बीच अंतर खोजना होगा। आपको सरणी संख्याओं को फिर से व्यवस्थित करने की अनुमति है। ऐसे कि उनके मतभेदों का योग अधिकतम होना चाहिए।

अधिकतम योग = | a1 - a2 | + | a3 - a4 | + | एn-1 - एn | + | एn - ए १ |

उदाहरण  

arr[]={9, 8, 4, 2}
22

व्याख्या

हम दिए गए एरे को 9, 2, 8, 4 के रूप में व्यवस्थित कर सकते हैं, फिर यह देगा

| 9 - 2 | + | 2 - 8 | + | 8 - 4 | + | 4 - 9 | = 22

एक गोलाकार सरणी में लगातार अंतर का योग अधिकतम करेंपिन

कलन विधि  

1. Set a variable output to 0.
2. Sort the given array.
3. Traverse up to n/2 length of the array(n is the length of the array).
    1. Sum up the value of output and array’s last values and store it to sum.
    2. Get the difference of output and twice of array’s starting value and store it to the output.
4. Return the value of output.

व्याख्या  

देखते हुए सरणी of पूर्णांकों। सरणी को एक माना जाना चाहिए गोलाकार सरणी जो कि अंतिम तत्व के बाद सीधे पहले तत्व को ट्रेस किया जा सकता है। हमें लगातार तत्वों के बीच अंतरों का अधिकतम योग खोजने के लिए कहा गया है। और सरणी को फिर से व्यवस्थित करने के लिए हमारे पास लाभ है। ऐसे कि हम मतभेदों के योग को बढ़ा सकते हैं।

यह भी देखें
आइसोमॉर्फिक स्ट्रिंग्स लेटेकोड सॉल्यूशन

यहाँ हमने एक सरणी दी है। हम वास्तव में सरणी को पुनर्व्यवस्थित नहीं करने जा रहे हैं, हम बस इसकी संख्याओं के साथ खेल सकते हैं। अब हम सरणी के केवल आधे भाग पर जा रहे हैं। यह उस सरणी की n / 2 लंबाई तक है जहाँ n सरणी की वास्तविक लंबाई है। हमने आउटपुट नामक एक चर घोषित किया है। जिसे व्यूह के अंतर मिलने वाले हैं। और फिर उस राशि को जमा करें और इसे आउटपुट में स्टोर करें। लेकिन सरणी को ट्रेस करने से पहले हम सरणी को क्रमबद्ध करने जा रहे हैं। हम सरणी को ऐसे क्रमबद्ध करने जा रहे हैं कि यह बढ़ते क्रम में होनी चाहिए। उपरांत छँटाई जिस सरणी में हमारे पास संख्या सबसे कम है वह सरणी के आरंभ में है। और सरणी में अधिक संख्या सरणी के अंत में है।

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

कोड  

C ++ कोड एक गोलाकार सरणी में निरंतर अंतर के योग को अधिकतम करने के लिए

#include<iostream>
#include<algorithm>

using namespace std;

int getMaxDiff(int arr[], int n)
{
    int output = 0;

    sort(arr, arr + n);

    for (int i = 0; i < n/2; i++)
    {
        output -= (2 * arr[i]);
        output += (2 * arr[n - i - 1]);
    }

    return output;
}
int main()
{
    int arr[] = { 9, 8, 2, 4 };
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getMaxDiff(arr, n) << endl;
    return 0;
}
22

एक गोलाकार सरणी में निरंतर अंतर के योग को अधिकतम करने के लिए जावा कोड

import java.util.Arrays;

class maximumDiff
{
    public static int getMaxDiff(int arr[], int n)
    {
        int output = 0;

        Arrays.sort(arr);

        for (int i = 0; i < n/2; i++)
        {
            output -= (2 * arr[i]);
            output += (2 * arr[n - i - 1]);
        }

        return output;
    }
    public static void main (String[] args)
    {
        int arr[] = {9, 8, 2, 4 };
        int n = arr.length;
        System.out.println(getMaxDiff(arr, n));
    }
}
22

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

समय जटिलता

ओ (एन लॉग एन) जहां "N" सरणी में तत्वों की संख्या है। क्योंकि हमने सरणी को क्रमबद्ध कर लिया है। तो समय जटिलता मर्ज की तरह हो जाती है। चूँकि वह समय जटिलता की ऊपरी सीमा को चिह्नित करता है।

यह भी देखें
वर्ड मैचिंग द्वारा शब्द का उपयोग करते हुए सबसे लंबा सामान्य उपसर्ग

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

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