Должина на најголемата под-низа со соседни елементи


Ниво на тешкотија Медиум
Често прашувано во Adobe Амазон Блумберг Cisco Карат Решенија за монотип Исплата PayU Публицис Сапиент SAP лаборатории
Низа Хаш

Проблемот „Должина на најголемата под-низа со соседни елементи“ наведува дека ви е даден број низа. Изјавата за проблемот бара да се открие должината на најдолгата соседна под-низа од кои елементи може да се распоредат во низа (континуирано, или растечки или опаѓачки). Броевите во низата можат да се појават повеќе пати.

пример

Должина на најголемата под-низа со соседни елементи

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

Објаснување

Бројот почнувајќи од 0-ти индекс до 3-ти индекс содржи броеви 10, 12, 13, 11 кои можат да се распоредат на начин 10, 11, 12, 13 од кои должината станува 4.

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

Објаснување

Бројот почнувајќи од 1-ви индекс до 3-ти индекс содржи броеви 1, 3, 2 кои можат да се распоредат на начин 1, 2, 3 од кои должината станува 3.

Алгоритам

  1. Намести максимална должина да 1.
  2. Отворете јамка, i = 0, додека јас <l -1,
    1. Прогласи а Намести и додадете arr [i] во Поставете.
    2. Поставете ја вредноста на максилен минлен да arr [i].
    3. Отворете јамка, почнувајќи од j = i + 1, додека j <l,
      1. Проверете дали Постави има вредност на arr [j],
        1. Ако е точно, скрши.
        2. Друго,
          1. Додадете го arr [j] во Постави.
          2. Откријте го минимумот помеѓу минлен и arr [j] и чувајте го до минлен.
          3. Откријте го максимумот помеѓу максилен и arr [j] и чувајте го на максилен.
          4. Проверете дали maxlen-min = = j - i
            1. Ако е точно, тогаш дознајте го максимумот помеѓу maxLength и max-minlen +1 и зачувајте го на maxLength.
  3. Врати maxLength.

Објаснување

Дадено е прашање што бара да ја откриеме должината на најдолгата соседна под-низа која има некои броеви што можат да се распоредат во низа. Може да има случај дадената низа да има дупликати броеви. Треба да се справиме и со тој случај. За да го добиеме решението, ќе користиме a Намести и вгнездена јамка што ќе се грижи за дупликат елементи.

Да разгледаме пример:

пример

Arr [] = {10, 12, 13, 11, 8, 10}

Useе користиме Set откако ќе отвориме јамка и ќе го додадеме бројот, еден по еден, и ќе ги поставиме вредностите на maxlen и minlen на arr [i]. Потоа отворете вметната јамка почнувајќи од еден елемент пред тековниот, бидејќи ние веќе го вметнавме тековниот елемент во Постави. Проверете дали Постави ја содржи вредноста на arr [j], ако е пронајден елемент, па скрши. Друго вметнете ја вредноста на arr [j] во Set и дознајте ја максимумот помеѓу maxlen и arr [j], а исто така минимална помеѓу minlen и arr [j] и зачувајте ја на maxlen и minlen, соодветно. Проверете дали maxlen-min е еднаква на ji, а потоа ажурирајте ја вредноста на maxLength.

maxLength = 1.

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

j = i + 1 = 1, ако mySet ќе има 12, не е лажно,

Така, вметнете 12 во mySet и пронајдете максимум 12 и 10 и минимум и складирајте 12 во максилен и 10 во минлен и проверете дали максилен-милен е еднаков на j - i, но тоа е погрешно.

j = 2, ако mySet ќе има 13, е лажно,

Така, вметнете 13 во mySet и пронајдете максимум 13 и 12 и складирајте 13 во максилен и 10 во минлен и проверете дали максилен-милен е еднаков на j - i е лажно.

j = 3, ако mySet ќе има 11, е лажно,

Така, вметнете 11 во mySet и пронајдете максимум 11 и 10 и складирајте 13 во максилен и 10 во минлен и проверете дали максилен-милен е еднаков на j - i е точно затоа што 13-10 е еднакво на 3-0. Значи, ажурирајте ја maxLength со откривање на максимум maxLength и maxlen-minlen + 1 max (1, 13-10 + 1) и се покажа дека е 4 и 4 се зачувани во maxLength и тој ќе продолжи да ја разгледува низата и поставете се додека не најде подолга должина од оваа на соседната под-низа.

Излез: 4

Код

C ++ код за наоѓање на должината на најголемата под-низа со соседни елементи

#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

Анализа на сложеност

Временска комплексност

На2) каде „Н“ е бројот на елементи во низата.

Комплексноста на просторот

Тој) каде „Н“ е бројот на елементи во низата.