مجموع اختلافات متوالی را در یک آرایه دایره ای به حداکثر برسانید  


سطح دشواری ساده
اغلب در کادنس هند ای بی GE بهداشت و درمان عیار Quora آزمایشگاههای SAP مربع
صف حریص مرتب سازی

بیان مسأله  

فرض کنید شما یک عدد صحیح صف. با این آرایه باید به صورت a رفتار کرد آرایه دایره ای. آخرین مقدار یک آرایه به اولین آرایه متصل خواهد شد ، 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 عدد صحیح. با آرایه باید به صورت a رفتار کرد آرایه دایره ای که می تواند مستقیماً بعد از آخرین عنصر به اولین عنصر رد شود. از ما خواسته شده است که حداکثر مجموع اختلافات بین عناصر متوالی را پیدا کنیم. و ما این مزیت را داریم که آرایه را مرتب کنیم. به گونه ای که بتوانیم مجموع اختلافات را به حداکثر برسانیم.

همچنین مشاهده کنید
رشته های ایزومورفیک محلول کد کد

در اینجا ما یک آرایه داده ایم. ما واقعاً ترتیب مرتب سازی آرایه را نمی دهیم ، می توانیم به سادگی با اعداد آن بازی کنیم. اکنون می خواهیم فقط نیمی از آرایه را رد کنیم. این فقط تا 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

تحلیل پیچیدگی  

پیچیدگی زمان

O (n log n) جایی که "n" تعداد عناصر آرایه است. زیرا ما آرایه را مرتب کرده ایم. بنابراین پیچیدگی زمانی مانند نوع ادغام می شود. از آنجا که این مرز بالایی از پیچیدگی زمان است.

همچنین مشاهده کنید
طولانی ترین پیشوند مشترک با استفاده از Word توسط Word Matching

پیچیدگی فضا

O (1) زیرا فضای اضافی مورد نیاز نیست. بنابراین پیچیدگی فضای مورد نیاز الگوریتم ثابت است. اما پیچیدگی فضایی کل برنامه خطی است.