ການກໍ່ສ້າງຂອງການເພີ່ມຂື້ນທີ່ຍາວທີ່ສຸດ (N log N)


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ Amazon ທະນາຄານ BankBazaar Paytm Samsung
Array ການຄົ້ນຫາຖານສອງ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

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

ເຈົ້າຍັງບໍ່ໄດ້ໃຫ້ array of integers. ບັນຫາ“ ການກໍ່ສ້າງຂອງການເພີ່ມຂື້ນທີ່ຍາວທີ່ສຸດ (N log N)” ຂໍໃຫ້ສ້າງການຕິດຕາມທີ່ເພີ່ມຂື້ນທີ່ຍາວທີ່ສຸດ.

ຍົກຕົວຢ່າງ

arr[]={1, 4, 7, 2, 9, 6, 12, 3 }
12, 9, 7, 4, 1 and the size of this longest increasing subsequence is 5.

ຄໍາອະທິບາຍ

ພວກເຮົາຄົ້ນພົບວ່າການຕິດຕໍ່ກັນທີ່ຍາວທີ່ສຸດແມ່ນ ກຳ ລັງເພີ່ມຂື້ນເປັນແຖວ.

ການກໍ່ສ້າງຂອງການເພີ່ມຂື້ນທີ່ຍາວທີ່ສຸດ (N log N)

ສູດການຄິດໄລ່ ສຳ ລັບການກໍ່ສ້າງໃນໄລຍະຍາວທີ່ສຸດທີ່ສຸດ (N log N)

1. Create two arrays lastIndexes and firstIndexes of size n, and initialize both of the arrays with 0 and -1 respectively.
2. Traverse the array from 1 to n(length of the array).
  1. Check if the current array element is less than the arr[lastIndexes[0]], if true, then update lastIndexes[0]=1.
  2. Check if the arr[i] is greater than the arr[lastIndexes[leng-1]], do the following
    1. Set the firstIndexes[i] to lastIndexes[leng-1].
    2. lastIndexes[leng++] = i.
  3. Else get the position of arr[i] using binary search and do the following.
    1. Update the value at firstIndexes[i] to lastIndexes[position-1].
    2. Update the value of the lastIndexes[position] to i.
3. Print the array, by initializing the value of i to the firstIndexes[i].

ຄໍາອະທິບາຍ

ພວກເຮົາໄດ້ມອບໂຕເລກລວມແລະພວກເຮົາໄດ້ຂໍໃຫ້ກໍ່ສ້າງ ຕໍ່ມາເພີ່ມຂຶ້ນທີ່ຍາວທີ່ສຸດ. ສຳ ລັບສິ່ງນີ້, ພວກເຮົາຈະ ນຳ ໃຊ້ສອງຮູບແບບ lastIndexes ແລະ firstIndexes ສອງແຖວແລະຕື່ມຂໍ້ມູນໃສ່ມັນດ້ວຍມູນຄ່າ 0 ແລະ -1 ຕາມ ລຳ ດັບ. firstIndexes array ຈະຖືກເລີ່ມຕົ້ນເປັນ 1. ເພາະວ່ານີ້ຈະເປັນການເກັບຮັກສາຄ່າຕ່າງໆຕາມ ຕຳ ແໜ່ງ ເປັນດັດສະນີ. ພວກເຮົາຈະໄດ້ຮັບການປັບປຸງຄຸນຄ່າຕ່າງໆໃນຂະນະທີ່ ກຳ ລັງເດີນຕາມແຖວ.

ພວກເຮົາ ກຳ ລັງກ້າວຂ້າມອາເລຈາກ 1 ເຖິງ n. ບ່ອນທີ່ n ແມ່ນຄວາມຍາວຂອງຂບວນ. ໃນຂະນະທີ່ ກຳ ລັງແລ່ນຜ່ານ, array lastIndexes ຈະຖືກ ນຳ ໃຊ້ເປັນ ຕຳ ແໜ່ງ ຫລືດັດສະນີຂອງຂບວນ. ພວກເຮົາຈະກວດເບິ່ງບາງເງື່ອນໄຂທີ່ພວກເຮົາ ກຳ ລັງຈະກວດສອບຖ້າວ່າປັດຈຸບັນອາເລນຕ່ ຳ ກວ່າອາຄານຂອງ lastIndexes [leng-1]. ຄວາມຍາວແມ່ນຖືກ ກຳ ນົດໃນເບື້ອງຕົ້ນວ່າ 1, ຊຶ່ງ ໝາຍ ຄວາມວ່າຢ່າງ ໜ້ອຍ ພວກເຮົາຈະມີຄວາມຍາວຕໍ່ໄປ 1. ດັ່ງນັ້ນຖ້າສະພາບຂ້າງເທິງນີ້ແມ່ນຄວາມຈິງແລ້ວກໍ່ປັບປຸງຂໍ້ມູນສຸດທ້າຍ [0] ເປັນ 1.

ພວກເຮົາ ຈຳ ເປັນຕ້ອງກວດເບິ່ງວ່າ arr [i] ແມ່ນໃຫຍ່ກວ່າຂບວນຂອງ lastIndexes [n-1]. ຫຼັງຈາກນັ້ນປັບປຸງທັງສອງແຖວ, ຕັ້ງຄ່າ FirstIndexes [i] ໃຫ້ກັບມູນຄ່າສຸດທ້າຍຂອງ lastIndexes [n-1] ແລະ lastIndexes [leng] ໃຫ້ຂ້ອຍແລະເພີ່ມມູນຄ່າຂອງຄ່າ leng. ອື່ນພວກເຮົາຕ້ອງຊອກຫາ ຕຳ ແໜ່ງ Element Element ປະຈຸບັນ. ສຳ ລັບສິ່ງນີ້, ພວກເຮົາຈະ ນຳ ໃຊ້ການຄົ້ນຫາຖານສອງແລະ ນຳ ເອົາດັດຊະນີນັ້ນເຂົ້າໃນ ຕຳ ແໜ່ງ. ແລະປັບປຸງຄຸນຄ່າຂອງ lastIndexes [ຕຳ ແໜ່ງ -1] ໃຫ້ firstIndexes [i] ແລະ lastIndexes [ຕຳ ແໜ່ງ] ໃຫ້ i.

ຫຼັງຈາກ traversal ພວກເຮົາຈໍາເປັນຕ້ອງໄດ້ພິມ array. ສຳ ລັບສິ່ງນີ້ພວກເຮົາຈະຜ່ານຈາກອັນດັບສຸດທ້າຍໄປ 0th ຕໍາແຫນ່ງແລະການເລີ່ມຕົ້ນດັດສະນີແຕ່ລະອັນໄປຫາ firstIndexes [i] ຫຼັງຈາກທີ່ຜ່ານການຕິດຕາມແລະພິມແຕ່ລະຄ່າທີ່ເປັນໄປໄດ້ຂອງອາເລ.

ລະຫັດ

ລະຫັດ C ++ ສຳ ລັບການກໍ່ສ້າງຕໍ່ມາມີການເພີ່ມຂື້ນທີ່ຍາວທີ່ສຸດ (N log N)

#include<iostream>
#include<vector>

using namespace std;

int GetPosition(int arr[], vector<int>& T, int left, int right,int key)
{
    while (right - left > 1)
    {
        int mid = left + (right - left) / 2;
        if (arr[T[mid]] >= key)
            right = mid;
        else
            left = mid;
    }
    return right;
}
int LongestIncreasingSubsequence(int arr[], int n)
{
    vector<int> lastIndexes(n, 0);
    vector<int> firstIndexes(n, -1);

    int len = 1;
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < arr[lastIndexes[0]])
        {
            lastIndexes[0] = i;
        }
        else if (arr[i] > arr[lastIndexes[len - 1]])
        {
            firstIndexes[i] = lastIndexes[len - 1];
            lastIndexes[len++] = i;
        }
        else
        {
            int positon = GetPosition(arr, lastIndexes, -1, len - 1, arr[i]);
            firstIndexes[i] = lastIndexes[positon - 1];
            lastIndexes[positon] = i;
        }
    }
    cout << "Longest Increase Subsequence:" << endl;
    for (int i = lastIndexes[len - 1]; i >= 0; i = firstIndexes[i])
        cout << arr[i] << " ";
    cout << endl;

    cout<<"LIS size:\n";

    return len;
}
int main()
{
    int arr[] = { 1, 4, 7, 2, 9, 6, 12, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);

    cout<< LongestIncreasingSubsequence(arr, n);

    return 0;
}
Longest Increase Subsequence:
12 9 7 4 1
LIS size:
5

ລະຫັດ Java ສຳ ລັບການກໍ່ສ້າງຕໍ່ມາມີການເພີ່ມຂື້ນທີ່ຍາວທີ່ສຸດ (N log N)

import java.util.Arrays;

class LongestIncreasingSubsequence
{
    public static int GetPosition(int arr[], int T[], int left, int right, int key)
    {
        while (right - left > 1)
        {
            int mid = left + (right - left) / 2;
            if (arr[T[mid]] >= key)
                right = mid;
            else
                left = mid;
        }
        return right;
    }
    public static int getSubsequence(int arr[], int n)
    {
        int lastIndexes[] = new int[n];

        Arrays.fill(lastIndexes, 0);

        int firstIndexes[] = new int[n];

        Arrays.fill(firstIndexes, -1);

        int len = 1;

        for (int i = 1; i < n; i++)
        {
            if (arr[i] < arr[lastIndexes[0]])
                lastIndexes[0] = i;
            else if (arr[i] > arr[lastIndexes[len - 1]])
            {
                firstIndexes[i] = lastIndexes[len - 1];
                lastIndexes[len++] = i;
            }
            else
            {
                int positon = GetPosition(arr, lastIndexes, -1, len - 1, arr[i]);
                firstIndexes[i] = lastIndexes[positon - 1];
                lastIndexes[positon] = i;
            }
        }
        System.out.println("Longest Increasing Subsequence of given input");
        for (int i = lastIndexes[len - 1]; i >= 0; i = firstIndexes[i])
            System.out.print(arr[i] + " ");

        System.out.println();

        return len;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 7, 2, 9, 6, 12, 3 };
        int n = arr.length;

        System.out.print("LIS size:\n" + getSubsequence(arr, n)+"\n");
    }
}
Longest Increasing Subsequence of given input
12 9 7 4 1
LIS size:
5

 

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

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

O (n log n) ບ່ອນທີ່“ n” ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ໃຊ້ການຄົ້ນຫາຖານສອງເຊິ່ງເຮັດໃຫ້ພວກເຮົາມີປັດໃຈດ້ານ logarithmic. ແຕ່ຖ້າພວກເຮົາຕ້ອງໂທຫາການຄົ້ນຫາຖານສອງ ສຳ ລັບແຕ່ລະດັດນີ. ຫຼັງຈາກນັ້ນໃນກໍລະນີທີ່ບໍ່ດີທີ່ສຸດ, ຄວາມສັບສົນເວລາຈະເປັນ O (N log N).

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

O (n) ບ່ອນທີ່“ n” ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ດັ່ງທີ່ພວກເຮົາໄດ້ສ້າງສອງແຖວຊົ່ວຄາວ FirstIndexes ແລະ lastIndexes ຊົ່ວຄາວ. ຄວາມສັບສົນຂອງພື້ນທີ່ກາຍເປັນ ໂອ (N).