തുടർച്ചയായ ഘടകങ്ങളുള്ള ഏറ്റവും വലിയ സബ്‌റേയുടെ നീളം


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

“തുടർച്ചയായ ഘടകങ്ങളുള്ള ഏറ്റവും വലിയ സബ്‌റേയുടെ ദൈർ‌ഘ്യം” എന്ന പ്രശ്നം നിങ്ങൾ‌ക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു പൂർണ്ണസംഖ്യ ശ്രേണി. ഘടകങ്ങളുടെ ക്രമത്തിൽ ക്രമീകരിക്കാൻ കഴിയുന്ന ഏറ്റവും ദൈർഘ്യമേറിയ തുടർച്ചയായ ഉപ-അറേയുടെ ദൈർഘ്യം കണ്ടെത്താൻ പ്രശ്‌ന പ്രസ്താവന ആവശ്യപ്പെടുന്നു (തുടർച്ചയായത്, ആരോഹണം അല്ലെങ്കിൽ അവരോഹണം). അറേയിലെ അക്കങ്ങൾ‌ ഒന്നിലധികം തവണ സംഭവിക്കാം.

ഉദാഹരണം

തുടർച്ചയായ ഘടകങ്ങളുള്ള ഏറ്റവും വലിയ സബ്‌റേയുടെ നീളം

arr[] = {10, 12, 13, 11, 8, 10, 11, 10}
4

വിശദീകരണം

0 സൂചിക മുതൽ മൂന്നാം സൂചിക വരെയുള്ള സംഖ്യയിൽ 3, 10, 12, 13 അക്കങ്ങൾ അടങ്ങിയിരിക്കുന്നു, അവ 11, 10, 11, 12 രീതിയിൽ ക്രമീകരിക്കാം, അതിൽ നീളം 13 ആയി മാറുന്നു.

arr[] = {1, 1, 3, 2, 8, 4, 8, 10}
3

വിശദീകരണം

ആദ്യ സൂചിക മുതൽ മൂന്നാം സൂചിക വരെയുള്ള സംഖ്യയിൽ 1, 3, 1 അക്കങ്ങൾ അടങ്ങിയിരിക്കുന്നു, അവ 3, 2, 1 രീതിയിൽ ക്രമീകരിക്കാം, അതിൽ നീളം 2 ആയി മാറുന്നു.

അൽഗോരിതം

  1. ഗണം പരമാവധി നീളം 1 ലേക്ക്.
  2. ഒരു ലൂപ്പ് തുറക്കുക, i = 0, ഞാൻ <l -1,
    1. ഒരു പ്രഖ്യാപിക്കുക ഗണം സെറ്റിലേക്ക് arr [i] ചേർക്കുക.
    2. ഇതിന്റെ മൂല്യം സജ്ജമാക്കുക maxlen ഒപ്പം minlen to arr [i].
    3. J = i + 1 മുതൽ j <l മുതൽ ആരംഭിച്ച് ഒരു ലൂപ്പ് തുറക്കുക
      1. സെറ്റിന് arr [j] ന്റെ മൂല്യമുണ്ടോയെന്ന് പരിശോധിക്കുക,
        1. ശരിയാണെങ്കിൽ, തകർക്കുക.
        2. അല്ലെങ്കിൽ,
          1. സെറ്റിലേക്ക് arr [j] ചേർക്കുക.
          2. മിന്നലിനും അറ [j] നും ഇടയിലുള്ള ഏറ്റവും കുറഞ്ഞത് കണ്ടെത്തി അത് മിനലിലേക്ക് സംഭരിക്കുക.
          3. മാക്‌സ്‌ലെനും അറയും തമ്മിലുള്ള പരമാവധി എണ്ണം കണ്ടെത്തി അത് മാക്‌സ്‌ലെനിൽ സംഭരിക്കുക.
          4. Maxlen-min = = j - i ആണോയെന്ന് പരിശോധിക്കുക
            1. ശരിയാണെങ്കിൽ മാക്‌സ്‌ലെംഗിനും മാക്‌സ്-മിൻലെൻ +1 നും ഇടയിലുള്ള പരമാവധി കണ്ടെത്തി അത് പരമാവധി ദൈർഘ്യത്തിലേക്ക് സംഭരിക്കുക.
  3. പരമാവധി ദൈർഘ്യം നൽകുക.

വിശദീകരണം

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

നമുക്ക് ഒരു ഉദാഹരണം നോക്കാം:

ഉദാഹരണം

വര് [] = {10, 12, 13, 11, 8, 10}

ഒരു ലൂപ്പ് തുറന്നതിനുശേഷം ഞങ്ങൾ ഒരു സെറ്റ് ഉപയോഗിക്കുകയും ഒരു സമയം നമ്പർ ചേർക്കുകയും മാക്സ്ലെൻ, മിൻലെൻ എന്നിവയുടെ മൂല്യം അറയിലേക്ക് സജ്ജമാക്കുകയും ചെയ്യും [i]. നിലവിലെ ഘടകത്തെക്കാൾ ഒരു ഘടകത്തിൽ നിന്ന് ആരംഭിച്ച് ഒരു നെസ്റ്റഡ് ലൂപ്പ് തുറക്കുക, കാരണം ഞങ്ങൾ ഇതിനകം നിലവിലുള്ള ഘടകത്തെ സെറ്റിലേക്ക് ചേർത്തു. സെറ്റിൽ arr [j] ന്റെ മൂല്യം ഉണ്ടോയെന്ന് പരിശോധിക്കുക, ഘടകം കണ്ടെത്തിയാൽ തകർക്കുക. അല്ലാത്തപക്ഷം സെറ്റിലേക്ക് അറയുടെ മൂല്യം തിരുകുക, മാക്‌സ്‌ലെൻ, ആർ [ജെ] എന്നിവയ്ക്കിടയിലുള്ള പരമാവധി എണ്ണം കണ്ടെത്തുക, കൂടാതെ മിന്നലിനും അർജറിനും ഇടയിലുള്ള ഏറ്റവും കുറഞ്ഞത് കണ്ടെത്തുകയും യഥാക്രമം മാക്‌സ്‌ലെൻ, മിൻലെൻ എന്നിവയിൽ സൂക്ഷിക്കുകയും ചെയ്യുക. മാക്‌സ്‌ലെൻ-മി ജിക്ക് തുല്യമാണോയെന്ന് പരിശോധിക്കുക, തുടർന്ന് മാക്‌സ്‌ലെംഗിന്റെ മൂല്യം അപ്‌ഡേറ്റുചെയ്യുക.

maxLength = 1.

i = 0, mySet = {10}, minlen = 10, maxlen = 10

j = i + 1 = 1, മൈസെറ്റിന് 12 ഉണ്ടെങ്കിൽ അത് തെറ്റാണ്,

അതിനാൽ മൈസെറ്റിലേക്ക് 12 തിരുകുക, പരമാവധി 12 ഉം 10 ഉം ഏറ്റവും കുറഞ്ഞത് കണ്ടെത്തുകയും 12 മാക്സ്ലെനിലേക്കും 10 മിനെലനിലേക്കും സംഭരിക്കുകയും മാക്സ്ലെൻ-മിൻലെൻ ജെ - ഐക്ക് തുല്യമാണോയെന്ന് പരിശോധിക്കുക, പക്ഷേ അത് തെറ്റാണ്.

j = 2, മൈസെറ്റിന് 13 ഉണ്ടെങ്കിൽ അത് തെറ്റാണ്,

അതിനാൽ 13 സെറ്റ് മൈസെറ്റിലേക്ക് തിരുകുക, പരമാവധി 13 ഉം 12 ഉം കണ്ടെത്തി 13 മാക്സ്ലെനിലും 10 എണ്ണം മിനെലനിലുമായി സംഭരിക്കുക, മാക്സ്ലെൻ-മിൻലെൻ ജെക്ക് തുല്യമാണോയെന്ന് പരിശോധിക്കുക - ഞാൻ തെറ്റാണ്.

j = 3, മൈസെറ്റിന് 11 ഉണ്ടെങ്കിൽ അത് തെറ്റാണ്,

അതിനാൽ മൈസെറ്റിലേക്ക് 11 തിരുകുക, പരമാവധി 11 ഉം 10 ഉം കണ്ടെത്തുക, 13 മാക്സ്ലെനിലേക്കും 10 മിനെലനിലേക്കും സംഭരിക്കുക, മാക്സ്ലെൻ-മിൻലെൻ ജെക്ക് തുല്യമാണോയെന്ന് പരിശോധിക്കുക - ഞാൻ ഇപ്പോൾ ശരിയാണ്, കാരണം 13-10 3-0 ന് തുല്യമാണ്. അതിനാൽ പരമാവധി ദൈർ‌ഘ്യവും മാക്‍സ്‌ലെൻ‌-മിൻ‌ലെൻ‌ + 1 മാക്സും (1, 13-10 + 1) കണ്ടെത്തുന്നതിലൂടെ മാക്‍സ്‌ലെംഗ്ത് അപ്‌ഡേറ്റുചെയ്യുക, ഇത് 4 ആണെന്നും 4 ഉം മാക്‌സ്‌ലെംഗിലേക്ക് സംഭരിക്കപ്പെടുന്നുവെന്നും ഇത് അറേയിലൂടെ സഞ്ചരിക്കുമെന്നും തുടർച്ചയായ ഉപ-അറേയേക്കാൾ ദൈർഘ്യമേറിയ ദൈർഘ്യം കണ്ടെത്തുന്നതുവരെ സജ്ജമാക്കുക.

Put ട്ട്‌പുട്ട്: 4

കോഡ്

തുടർച്ചയായ ഘടകങ്ങളുള്ള ഏറ്റവും വലിയ സബ്‌റേയുടെ നീളം കണ്ടെത്താൻ സി ++ കോഡ്

#include<set>
#include<iostream>

using namespace std;

int getLongestLength(int arr[], int l)
{
    int maxLength = 1;
    for (int i=0; i<l-1; i++)
    {
        set<int> mySet;
        mySet.insert(arr[i]);
        int minlen = arr[i], maxlen = arr[i];

        for (int j=i+1; j<l; j++)
        {
            if (mySet.find(arr[j]) != mySet.end())
                break;

            mySet.insert(arr[j]);
            minlen = min(minlen, arr[j]);
            maxlen = max(maxlen, arr[j]);

            if (maxlen - minlen == j - i)
                maxLength = max(maxLength, maxlen - minlen + 1);
        }
    }
    return maxLength;
}
int main ()
{
    int arr[] = {10, 12, 13, 11, 8, 10};
    int l = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the Longest contiguous Sub-Array is: " << getLongestLength(arr, l);
    return 0;
}
Length of the Longest contiguous Sub-Array is: 4

തുടർച്ചയായ ഘടകങ്ങളുള്ള ഏറ്റവും വലിയ സബ്‌റേയുടെ നീളം കണ്ടെത്താൻ ജാവ കോഡ്

import java.util.HashSet;

class largestSubArrayContiguousElements
{
    public static int getLongestLength(int arr[])
    {
        int l = arr.length;
        int maxLength = 1;

        for (int i=0; i< l-1; i++)
        {
            HashSet<Integer> mySet = new HashSet<>();
            mySet.add(arr[i]);

            int min = arr[i];

            int max = arr[i];

            for (int j=i+1; j<l; j++)
            {
                if (mySet.contains(arr[j]))
                    break;

                mySet.add(arr[j]);
                min = Math.min(min, arr[j]);
                max = Math.max(max, arr[j]);

                if (max-min == j-i)
                    maxLength = Math.max(maxLength, max-min+1);
            }
        }
        return maxLength;
    }
    public static void main (String[] args)
    {
        int arr[] = {10, 12, 13, 11, 8, 10};
        System.out.println("Length of the Longest contiguous SubArray is: "+getLongestLength(arr));
    }
}
Length of the Longest contiguous SubArray is: 4

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n2) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.

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

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.