تعظيم مجموع الاختلافات المتتالية في مصفوفة دائرية


مستوى الصعوبة سهل
كثيرا ما يطلب في إيقاع الهند يباي جنرال إلكتريك للرعاية الصحية قيراط قرة مختبرات SAP مربع
مجموعة طامع فرز

المشكلة بيان

افترض أن لديك ملف عدد صحيح مجموعة. يجب التعامل مع هذه المصفوفة على أنها ملف مجموعة دائرية. سيتم توصيل القيمة الأخيرة للمصفوفة بالمصفوفة الأولى ، an ⇒ a1. تطلب مسألة "تعظيم مجموع الفروق المتتالية في مصفوفة دائرية" معرفة الحد الأقصى لمجموع الفرق بين كل عنصر متتالي. لذلك عليك أن تجد الفرق بين عنصر متتالي. يُسمح لك بإعادة ترتيب أرقام المصفوفة. بحيث يجب أن يكون مجموع اختلافاتهم كحد أقصى.

أقصى مبلغ = | a1 - a2 | + | a3 - a4 | + | أn-1 - أn | + | أn - a1 |

مثال

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

كود Java لتعظيم مجموع الاختلافات المتتالية في مصفوفة دائرية

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

تحليل التعقيد

تعقيد الوقت

س (ن سجل ن) أين "ن" هو عدد العناصر في المصفوفة. لأننا قمنا بفرز المصفوفة. لذا فإن تعقيد الوقت يصبح مثل التعقيد في نوع الدمج. بما أن هذا يمثل الحد الأعلى لتعقيد الوقت.

تعقيد الفضاء

يا (1) حيث لا توجد مساحة إضافية مطلوبة. لذا فإن تعقيد المساحة الذي تتطلبه الخوارزمية ثابت. لكن التعقيد المكاني للبرنامج بأكمله خطي.