Дужина највећег низа са суседним елементима


Ниво тешкоће Средњи
Често питани у адобе амазонка Блоомберг Цисцо карат Монотипска решења Паитм ПаиУ Публицис Сапиент САП Лабс
Ред Хасх

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

Пример

Дужина највећег низа са суседним елементима

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. Сет максимална дужина да КСНУМКС.
  2. Отворите петљу, и = 0, док је и <л -1,
    1. Изјавите а Сет и додајте арр [и] у Сет.
    2. Подесите вредност маклен минлен да дођу [и].
    3. Отворите петљу, почевши од ј = и + 1, док ј <л,
      1. Проверите да ли Сет има вредност арр [ј],
        1. Ако је тачно, сломи.
        2. Елсе,
          1. Додајте арр [ј] у Сет.
          2. Пронађите минимум између минлена и арр [ј] и спремите га у минлен.
          3. Пронађите максимум између маклена и арр [ј] и сачувајте га у маклен.
          4. Проверите да ли је маклен-мин = = ј - и
            1. Ако је тачно, сазнајте максимум између макЛенгтх и мак-минлен +1 и сачувајте га у макЛенгтх.
  3. Поврат макЛенгтх.

Објашњење

Добијамо питање које тражи да сазнамо дужину најдужег суседног низа који има неке бројеве који се могу поредати у низу. Може бити случај да дати низ има дупликате бројева. Морамо да се позабавимо и тим случајем. Да бисмо добили решење, користићемо а Сет и угнежђену петљу која ће се побринути за дупле елементе.

Размотримо пример:

Пример

Арр [] = {10, 12, 13, 11, 8, 10}

Користићемо Сет након отварања петље и додати број један по један и поставити вредност маклен и минлен на арр [и]. Затим отворите угнежђену петљу почевши од једног елемента испред тренутног елемента, јер смо тренутни елемент већ уметнули у Сет. Проверите да ли Сет садржи вредност арр [ј], ако је елемент пронађен, онда бреак. Иначе убаците вредност арр [ј] у Сет и сазнајте максимум између маклен и арр [ј], а такође и минимум између минлен и арр [ј] и сачувајте је у маклен и минлен респективно. Проверите да ли је маклен-мин једнак ји, а затим ажурирајте вредност макЛенгтх.

макЛенгтх = 1.

и = 0, миСет = {10}, минлен = 10, маклен = 10

ј = и + 1 = 1, ако ће миСет имати 12, је нетачно,

Дакле, уметните 12 у миСет и пронађите максимум 12 и 10, а најмање и похраните 12 у маклен и 10 у минлен и проверите да ли је маклен-минлен једнако ј - и, али је нетачно.

ј = 2, ако ће миСет имати 13, је нетачно,

Дакле, уметните 13 у миСет и пронађите максимум 13 и 12 и спремите 13 у маклен и 10 у минлен и проверите да ли је маклен-минлен једнако ј - и није тачно.

ј = 3, ако ће миСет имати 11, је нетачно,

Дакле, уметните 11 у миСет и пронађите максимум од 11 и 10 и спремите 13 у маклен и 10 у минлен и проверите да ли је маклен-минлен једнако ј - и сада је тачно јер је 13-10 једнако 3-0. Дакле, ажурирајте макЛенгтх тако што ћете сазнати максимум макЛенгтх и маклен-минлен + 1 мак (1, 13-10 + 1) и утврђено је да су 4 и 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

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

Сложеност времена

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

Сложеност простора

Он) где „Н“ је број елемената у низу.