ຜົນກະທົບຕໍ່ Bitonic ທີ່ຍາວທີ່ສຸດ


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ CodeNation DE Shaw ກູໂກ JP Morgan Microsoft
Array ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

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

ຍົກຕົວຢ່າງ

arr[] = {1,4,2,76,43,78,54,32,1,56,23}
7

ຄໍາອະທິບາຍ

1 4 76 78 54 32 23 (ຄັ້ງ ທຳ ອິດເພີ່ມຂື້ນເຖິງ 78 ແລະຫຼັງຈາກນັ້ນຫຼຸດລົງຈົນຮອດ 23.

ຜົນກະທົບຕໍ່ Bitonic ທີ່ຍາວທີ່ສຸດ

 

ລະບົບວິເຄາະ

  1. ປະກາດເປັນແຖວ ເພີ່ມຂື້ນ ຂອງຂະ ໜາດ ດຽວກັນກັບຄວາມຍາວຂອງຄວາມຍາວຂບວນທີ່ໃຫ້.
  2. ເລີ່ມຕົ້ນອົງປະກອບດັດສະນີທັງ ໝົດ ເປັນ 1 ຂອງອາເລທີ່ຖືກສ້າງຂື້ນ zuj zus ຂື້ນ [].
  3. ຊອກຫາການຕິດຕາມທີ່ເພີ່ມຂື້ນທີ່ຍາວທີ່ສຸດໂດຍການເກັບຮັກສາມັນຢູ່ໃນສະຖິຕິທີ່ເພີ່ມຂື້ນ [] ຈາກຊ້າຍຫາຂວາ.
  4. ປະກາດເປັນແຖວ ຫຼຸດລົງ Seq [] ຂອງຂະ ໜາດ ດຽວກັນກັບຄວາມຍາວຂອງອາເລທີ່ໃຫ້.
  5. ຊອກຫາການຫຼຸດລົງທີ່ຍາວທີ່ສຸດຕິດຕາມຈາກຂວາຫາຊ້າຍແລະໂດຍການເກັບຮັກສາມັນເຂົ້າໄປໃນ SSq ຫຼຸດລົງ.
  6. ເລີ່ມຕົ້ນຕົວແປທີ່ມີຊື່ວ່າ maxOutput ເພື່ອການເພີ່ມຂື້ນSeq [0] + ຫຼຸດລົງSeq [0] - 1.
  7. ຊອກຫາສູງສຸດຂອງ ເພີ່ມຂື້ນSeq [i] + ຫຼຸດລົງ Seq [i] - 1 ແລະເກັບຮັກສາມັນໄວ້ເພື່ອ maxOutput.
  8. ກັບໄປ maxOutput.

ຄໍາອະທິບາຍ

ແຖວການປ້ອນຂໍ້ມູນຂອງຂະ ໜາດ n ປະກອບດ້ວຍເລກບວກ. ພວກເຮົາຖືກຮ້ອງຂໍໃຫ້ຊອກຫາລໍາດັບຕົວຄູນທີ່ຍາວທີ່ສຸດຂອງອາເລທີ່ໃຫ້. ລໍາດັບຕົວຄູນສາມາດຖືກກໍານົດເປັນລໍາດັບທີ່ເພີ່ມຂື້ນກ່ອນ, ຊຶ່ງຫມາຍຄວາມວ່າຕົວເລກໃນລໍາດັບເພີ່ມຂື້ນກ່ອນ. ຫຼັງຈາກນັ້ນ, ຕົວເລກຫຼຸດລົງຈົນກ່ວາໃນຕອນທ້າຍຂອງລໍາດັບ. ພວກເຮົາຕ້ອງ ກຳ ນົດຄວາມຍາວຂອງ ລຳ ດັບ bitonic ທີ່ຍາວທີ່ສຸດ.

ຫນ້າທໍາອິດ, ແຍກວິທີແກ້ໄຂອອກເປັນສອງສ່ວນ. ພວກເຮົາປະກາດສອງອາຄານ, ແຖວ ທຳ ອິດຖືກພິຈາລະນາເປັນ ເພີ່ມຂື້ນSeq ຂບວນ. ລໍາດັບທີ່ເພີ່ມຂື້ນທີ່ຍາວທີ່ສຸດແມ່ນລໍາດັບເຊິ່ງຕົວເລກຄວນຢູ່ໃນລໍາດັບທໍາອິດທີ່ເພີ່ມຂື້ນ. ດັ່ງນັ້ນ, ພວກເຮົາ ກຳ ລັງຈະກ້າວຂ້າມອາເລນໃນວົງທີ່ມີຮັງ. ສືບຕໍ່ຊອກຫາທີ່ເພີ່ມຂື້ນຕໍ່ມາ. ຫຼັງຈາກນັ້ນພວກເຮົາຕ້ອງກວດເບິ່ງສະພາບການທີ່ວ່າຖ້າວ່າປັດຈຸບັນມີ ໜ້ອຍ ກວ່າອົງປະກອບຕໍ່ໄປ. ແລະອົງປະກອບປັດຈຸບັນທີ່ເພີ່ມຂື້ນຂອງSeqແມ່ນ ໜ້ອຍ ກວ່າອົງປະກອບຕໍ່ໄປຂອງການເພີ່ມຂື້ນຂອງ SSq []. ຖ້າເປັນຄວາມຈິງແລ້ວເກັບຮັກສາອົງປະກອບດັ່ງກ່າວໃຫ້ເພີ່ມຂື້ນSeq [j] + 1. ສິ່ງນີ້ເພີ່ມຂື້ນເພາະວ່າພວກເຮົາໄດ້ເລີ່ມຕົ້ນອາເລທີ່ເປັນ 1 ໃນນັ້ນ.

ສອງ, ປະກາດເປັນແຖວ, ຫຼຸດລົງ Seq []. ໃນການຫຼຸດລົງຂອງ Seq [] ນີ້, ພວກເຮົາ ກຳ ລັງກ້າວຂ້າມແຖວໃນແບບວົງຈອນຮັງ, ຈາກຂວາຫາຊ້າຍຂອງແຖວ. ພວກເຮົາຈະກວດສອບວ່າອົງປະກອບປັດຈຸບັນໃຫຍ່ກວ່າທາດຕໍ່ໄປ. ເພາະວ່າພວກເຮົາ ກຳ ລັງຂ້າມຈາກຂວາຫາຊ້າຍ. ຫຼັງຈາກນັ້ນ, ປັບປຸງມັນໃຫ້ຫຼຸດລົງSeq [i] ກັບການຫຼຸດລົງ seq [j] +1. ໃນຂັ້ນຕອນສຸດທ້າຍຂອງລະຫັດ, ພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຫາສູງສຸດຂອງການເພີ່ມຂື້ນສູງສຸດຂອງ [s] + ຫຼຸດລົງ Seq [i] - 1 ເຊິ່ງເກັບໄວ້ໃນ maxOutput.

ລະຫັດ

ລະຫັດ C ++ ສຳ ລັບຜົນຕໍ່ມາຂອງ Bitonic ທີ່ຍາວທີ່ສຸດ

#include<iostream>

using namespace std;

int BitonicSequence( int arr[], int n )
{
    int i, j;

    int *increasingSeq = new int[n];
    for (i = 0; i < n; i++)
        increasingSeq[i] = 1;

    for (i = 1; i < n; i++)
        for (j = 0; j < i; j++)
            if (arr[i] > arr[j] && increasingSeq[i] < increasingSeq[j] + 1)
                increasingSeq[i] = increasingSeq[j] + 1;

    int *decreasingSeq = new int [n];
    for (i = 0; i < n; i++)
        decreasingSeq[i] = 1;

    for (i = n-2; i >= 0; i--)
        for (j = n-1; j > i; j--)
            if (arr[i] > arr[j] && decreasingSeq[i] < decreasingSeq[j] + 1)
                decreasingSeq[i] = decreasingSeq[j] + 1;

    int maxOutput = increasingSeq[0] + decreasingSeq[0] - 1;

    for (i = 1; i < n; i++)
        if (increasingSeq[i] + decreasingSeq[i] - 1 > maxOutput)
            maxOutput = increasingSeq[i] + decreasingSeq[i] - 1;

    return maxOutput;

}
int main()
{
    int arr[] = {1,4,2,76,43,78,54,32,1,56,23};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"Length of Longest Bitonic Sequence is "<< BitonicSequence(arr, n);
    return 0;
}
Length of Longest Bitonic Sequence is 7

ລະຫັດ Java ສຳ ລັບຜົນຕໍ່ມາຂອງ Bitonic ທີ່ຍາວທີ່ສຸດ

class longestBitonicSequence
{
    public static int BitonicSequence( int arr[], int n )
    {
        int i, j;

        int[] increasingSeq = new int[n];
        for (i = 0; i < n; i++)
            increasingSeq[i] = 1;

        for (i = 1; i < n; i++)
            for (j = 0; j < i; j++)
                if (arr[i] > arr[j] && increasingSeq[i] < increasingSeq[j] + 1)
                    increasingSeq[i] = increasingSeq[j] + 1;

        int[] decreasingSeq = new int [n];
        for (i = 0; i < n; i++)
            decreasingSeq[i] = 1;

        for (i = n-2; i >= 0; i--)
            for (j = n-1; j > i; j--)
                if (arr[i] > arr[j] && decreasingSeq[i] < decreasingSeq[j] + 1)
                    decreasingSeq[i] = decreasingSeq[j] + 1;


        int maxOutput = increasingSeq[0] + decreasingSeq[0] - 1;

        for (i = 1; i < n; i++)
            if (increasingSeq[i] + decreasingSeq[i] - 1 > maxOutput)
                maxOutput = increasingSeq[i] + decreasingSeq[i] - 1;

        return maxOutput;
    }

    public static void main (String[] args)
    {
        int arr[] = {1,4,2,76,43,78,54,32,1,56,23};
        int n = arr.length;
        System.out.println("Length of longest bitonic sequence is "+ BitonicSequence( arr, n ));
    }
}
Length of longest bitonic sequence is 7

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

ໂອ (ນ2ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ເນື່ອງຈາກພວກເຮົາໃຊ້ loop ຮັງເຊິ່ງເຮັດໃຫ້ລະບົບ algorithm ເຮັດວຽກໃນເວລາ polynomial.

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

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ເນື່ອງຈາກວ່າພວກເຮົາ ນຳ ໃຊ້ອາຄານພິເສດສອງບ່ອນທີ່ຂະ ໜາດ ຂອງມັນຂື້ນກັບອາເລປະກອບ. ຄວາມສັບສົນຂອງພື້ນທີ່ແມ່ນເປັນເສັ້ນ.