ദൈർഘ്യമേറിയ വർദ്ധിച്ചുവരുന്ന തുടർന്നുള്ള നിർമ്മാണം (എൻ ലോഗ് എൻ)


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു ആമസോൺ ബാങ്ക്ബസാർ Paytm സാംസങ്
അറേ ബൈനറി തിരയൽ ഡൈനാമിക് പ്രോഗ്രാമിംഗ്

പ്രശ്നം പ്രസ്താവന

നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ട് ശ്രേണി of പൂർണ്ണസംഖ്യകൾ. “ദൈർഘ്യമേറിയ വർദ്ധിച്ചുവരുന്ന തുടർന്നുള്ള നിർമ്മാണം (എൻ ലോഗ് എൻ)” എന്ന പ്രശ്നം ഏറ്റവും ദൈർഘ്യമേറിയ തുടർച്ചയെ നിർമ്മിക്കാൻ ആവശ്യപ്പെടുന്നു.

ഉദാഹരണം

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

വിശദീകരണം

ഒരു ശ്രേണിയിൽ വർദ്ധിച്ചുകൊണ്ടിരിക്കുന്ന ഏറ്റവും ദൈർഘ്യമേറിയ തുടർച്ച ഞങ്ങൾ കണ്ടെത്തുന്നു.

ദൈർഘ്യമേറിയ വർദ്ധിച്ചുവരുന്ന തുടർന്നുള്ള നിർമ്മാണം (എൻ ലോഗ് എൻ)

ദൈർഘ്യമേറിയ വർദ്ധിച്ചുവരുന്ന തുടർന്നുള്ള നിർമ്മാണത്തിനുള്ള അൽഗോരിതം (എൻ ലോഗ് എൻ)

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].

വിശദീകരണം

ഞങ്ങൾ‌ ഒരു കൂട്ടം സംഖ്യകൾ‌ നൽ‌കി, നിർമ്മിക്കാൻ‌ ഞങ്ങൾ‌ ആവശ്യപ്പെട്ടു ഏറ്റവും ദൈർഘ്യമേറിയ തുടർച്ച. ഇതിനായി, ഞങ്ങൾ രണ്ട് അറേ ലാസ്റ്റ്ഇൻ‌ഡെക്സുകളും ഫസ്റ്റ് ഇൻ‌ഡെക്സുകളും ഉപയോഗിക്കുകയും യഥാക്രമം 0, -1 മൂല്യങ്ങൾ‌ പൂരിപ്പിക്കുകയും ചെയ്യും. firstIndexes അറേ 1 ആയി സമാരംഭിക്കും. കാരണം ഇത് മൂല്യങ്ങളെ സൂചികകളായി സ്ഥാനങ്ങളായി സംഭരിക്കും. അറേയിലൂടെ സഞ്ചരിക്കുമ്പോൾ ഞങ്ങൾ മൂല്യങ്ങൾ അപ്‌ഡേറ്റ് ചെയ്യും.

ഞങ്ങൾ 1 മുതൽ n വരെ അറേയിലൂടെ സഞ്ചരിക്കാൻ പോകുന്നു. ഇവിടെ n എന്നത് അറേയുടെ നീളം. സഞ്ചരിക്കുമ്പോൾ, അറേ ലാസ്റ്റ്ഇൻഡെക്സുകൾ ഒരു അറേയുടെ സ്ഥാനം അല്ലെങ്കിൽ സൂചികയായി ഉപയോഗിക്കും. നിലവിലെ അറേ ഘടകം ലാസ്റ്റ് ഇൻ‌ഡെക്സുകളുടെ [ലെംഗ് -1] അറേയേക്കാൾ കുറവാണോയെന്ന് പരിശോധിക്കാൻ പോകുന്ന ചില നിബന്ധനകൾ ഞങ്ങൾ പരിശോധിക്കും. ദൈർഘ്യം ആദ്യം 1 ആയി നിർവചിക്കപ്പെടുന്നു, അതിനർത്ഥം കുറഞ്ഞത് 1 ന്റെ തുടർച്ചയെങ്കിലും നമുക്ക് ഉണ്ടായിരിക്കുമെന്നാണ്. അതിനാൽ മുകളിലുള്ള വ്യവസ്ഥ ശരിയാണെങ്കിൽ അവസാന ഇൻഡെക്സുകൾ [0] 1 ലേക്ക് അപ്‌ഡേറ്റുചെയ്യുക.

അവസാന ഇൻഡെക്സുകളുടെ [n-1] അറേയേക്കാൾ വലിപ്പം വലുതാണോ എന്ന് പരിശോധിക്കേണ്ടതുണ്ട്. തുടർന്ന് രണ്ട് അറേകളും അപ്‌ഡേറ്റ് ചെയ്യുക, ഫസ്റ്റ് ഇൻഡെക്സുകൾ [i] ലാസ്റ്റ്ഇൻഡെക്സുകളുടെ അവസാന മൂല്യത്തിലേക്ക് [n-1], ലാസ്റ്റ്ഇൻഡെക്സുകൾ [ലെംഗ്] i ലേക്ക് സജ്ജമാക്കി ലെംഗ് മൂല്യത്തിന്റെ മൂല്യം വർദ്ധിപ്പിക്കുക. അല്ലെങ്കിൽ നിലവിലെ അറേ എലമെൻറ് സ്ഥാനം കണ്ടെത്തേണ്ടതുണ്ട്. ഇതിനായി, ഞങ്ങൾ ബൈനറി തിരയൽ ഉപയോഗിക്കുകയും ആ സൂചികയെ സ്ഥാനത്ത് എത്തിക്കുകയും ചെയ്യും. LastIndexes [position-1] ന്റെ മൂല്യം firstIndexes [i], lastIndexes [position] i എന്നിവയിലേക്ക് അപ്ഡേറ്റ് ചെയ്യുക.

ട്രാവെർസലിനുശേഷം നമ്മൾ അറേ പ്രിന്റുചെയ്യേണ്ടതുണ്ട്. ഇതിനായി ഞങ്ങൾ അവസാനത്തേത് മുതൽ 0 വരെ സഞ്ചരിക്കുംth ഓരോ സൂചികയും ഫസ്റ്റ്ഇൻഡെക്സിലേക്ക് [i] സ്ഥാപിക്കുകയും ആരംഭിക്കുകയും ചെയ്യുന്നു.

കോഡ്

ദൈർഘ്യമേറിയ വർദ്ധിച്ചുവരുന്ന തുടർന്നുള്ള നിർമ്മാണത്തിനായുള്ള സി ++ കോഡ് (എൻ ലോഗ് എൻ)

#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

ദൈർഘ്യമേറിയ വർദ്ധിച്ചുവരുന്ന തുടർന്നുള്ള നിർമ്മാണത്തിനുള്ള ജാവ കോഡ് (എൻ ലോഗ് എൻ)

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 ലോഗ് n) ഇവിടെ “n” എന്നത് അറേയിലെ ഘടകങ്ങളുടെ എണ്ണമാണ്. ബൈനറി തിരയൽ ഞങ്ങൾ ഉപയോഗിച്ചതിനാൽ ഇത് ഒരു ലോഗരിഥമിക് ഘടകം നൽകുന്നു. എന്നാൽ ഓരോ സൂചികയ്‌ക്കുമുള്ള ബൈനറി തിരയലിനെ വിളിക്കേണ്ടിവന്നാൽ. ഏറ്റവും മോശം അവസ്ഥയിൽ, സമയ സങ്കീർണ്ണത O (N log N) ആയിരിക്കും.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) ഇവിടെ “n” എന്നത് അറേയിലെ ഘടകങ്ങളുടെ എണ്ണമാണ്. ഞങ്ങൾ‌ രണ്ട് താൽ‌ക്കാലിക അറേകൾ‌ സൃഷ്‌ടിച്ചതുപോലെ ഫസ്റ്റ് ഇൻ‌ഡെക്സുകളും ലാസ്റ്റ് ഇൻ‌ഡെക്സുകളും. സ്ഥല സങ്കീർണ്ണത മാറുന്നു O (N).