රවුම් අරාවක අඛණ්ඩ වෙනස්කම්වල එකතුව උපරිම කරන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ කේඩන්ස් ඉන්දියාව ඊ බේ GE සෞඛ්යාරක්ෂණය කරට් කෝරා 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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (n ලොග් එන්) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. මොකද අපි අරාව වර්ග කරලා තියෙනවා. එබැවින් කාල සංකීර්ණත්වය ඒකාබද්ධ කිරීමේ වර්ගයට සමාන වේ. එය කාල සංකීර්ණයේ ඉහළ සීමාව සලකුණු කරන බැවින්.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1) අමතර ඉඩක් අවශ්‍ය නොවන බැවින්. එබැවින් ඇල්ගොරිතමයට අවශ්‍ය අවකාශ සංකීර්ණතාව නියත වේ. නමුත් සමස්ත වැඩසටහනේ අවකාශ සංකීර්ණතාව රේඛීය වේ.