ຂະຫຍາຍຜົນລວມຂອງຄວາມແຕກຕ່າງຕິດຕໍ່ກັນໃນຂບວນວົງມົນ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Cadence ອິນເດຍ eBay GE Healthcare ລັດ Quora ຫ້ອງທົດລອງ SAP Square
Array ຄວາມໂລບມາກ ຮຽງລໍາດັບ

ຖະແຫຼງການບັນຫາ

ສົມມຸດວ່າທ່ານມີ integer array. ອາເລນີ້ຄວນໄດ້ຮັບການຮັກສາເປັນກ ຂບວນວົງມົນ. ຄ່າສຸດທ້າຍຂອງອາເລຈະຖືກເຊື່ອມຕໍ່ກັບແຖວ ທຳ ອິດ, ກ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

ຂະຫຍາຍຜົນລວມຂອງຄວາມແຕກຕ່າງຕິດຕໍ່ກັນໃນຂບວນວົງມົນ

ລະບົບວິເຄາະ

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.

ຄໍາອະທິບາຍ

ມອບໃຫ້ array of integers. ຂບວນການດັ່ງກ່າວຄວນໄດ້ຮັບການຮັກສາເປັນກ ຂບວນວົງມົນ ເຊິ່ງສາມາດຜ່ານໄປຫາອົງປະກອບ ທຳ ອິດໂດຍກົງຫຼັງຈາກອົງປະກອບສຸດທ້າຍ. ພວກເຮົາໄດ້ຖືກຮ້ອງຂໍໃຫ້ຊອກຫາຜົນລວມສູງສຸດຂອງຄວາມແຕກຕ່າງລະຫວ່າງອົງປະກອບຕິດຕໍ່ກັນ. ແລະພວກເຮົາມີປະໂຫຍດໃນການຈັດແຈງແຖວ. ສິ່ງດັ່ງກ່າວທີ່ພວກເຮົາສາມາດເພີ່ມຍອດລວມຂອງຄວາມແຕກຕ່າງ.

ນີ້ພວກເຮົາໄດ້ຈັດແຈງແຖວ. ພວກເຮົາບໍ່ໄດ້ໄປຈັດແຈງແຖວຕົວຈິງ, ພວກເຮົາພຽງແຕ່ສາມາດຫຼີ້ນກັບຕົວເລກຂອງມັນ. ໃນປັດຈຸບັນພວກເຮົາກໍາລັງຈະຜ່ານພຽງແຕ່ເຄິ່ງຫນຶ່ງຂອງອາເລ. ນັ້ນແມ່ນພຽງແຕ່ເຖິງຄວາມຍາວ 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 log n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ເພາະວ່າພວກເຮົາໄດ້ຈັດຮຽງແຖວ. ສະນັ້ນຄວາມສັບສົນໃນເວລາກາຍເປັນຄືກັບການປະສົມປະສານກັນ. ເນື່ອງຈາກວ່ານັ້ນແມ່ນຂີດ ໝາຍ ດ້ານເທິງຂອງຄວາມສັບສົນເວລາ.

ຄວາມສັບສົນໃນອະວະກາດ

O (1) ຍ້ອນວ່າບໍ່ ຈຳ ເປັນຕ້ອງມີພື້ນທີ່ພິເສດ. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ທີ່ຕ້ອງການໂດຍວິທີຄິດໄລ່ແມ່ນຄົງທີ່. ແຕ່ຄວາມສັບສົນດ້ານພື້ນທີ່ຂອງໂປແກຼມທັງ ໝົດ ແມ່ນເປັນເສັ້ນ.