מקסם את סכום ההבדלים ברצף במערך מעגלי


רמת קושי קַל
נשאל לעתים קרובות קדנס הודו eBay GE Healthcare קראט Quora מעבדות SAP בצורת ריבוע
מערך חמדן מִיוּן

הצהרת בעיה

נניח שיש לך מספר שלם מערך. יש להתייחס למערך זה כאל מערך מעגלי. הערך האחרון של מערך יחובר למערך הראשון, אn ⇒ 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

ניתוח מורכבות

מורכבות זמן

O (n יומן n) איפה "N" הוא מספר האלמנטים במערך. כי מינינו את המערך. כך שמורכבות הזמן הופכת להיות כזו של מיזוג מיזוג. מכיוון שזה מסמן את הגבול העליון של מורכבות הזמן.

מורכבות בחלל

O (1) מכיוון שלא נדרש מקום נוסף. כך שמורכבות החלל הנדרשת על ידי האלגוריתם היא קבועה. אך מורכבות החלל של כל התוכנית היא לינארית.