Подсеквенца максималне дужине са разликом између суседних елемената као 0 или 1


Ниво тешкоће Средњи
Често питани у Цисцо Екпедиа Куалтрицс САП Лабс терадата
Ред Динамичко програмирање

Изјава о проблему

Добија се цео број поредак. Проблем „Подсеквенца максималне дужине са разликом између суседних елемената као 0 или 1“ тражи да се утврди максимална дужина подсекције са разликом између суседних елемената не би требало да буде другачија од 0 или 1.

Пример

arr[] = {1, 4, 5, 2, 6, 5, 4, 8}
5

Објашњење

Подредност = 4, 5, 6, 5, 4

arr[] = {1, -3, -2, 0, -1, -2, -3, -4}
6

Објашњење

Подредност = -3, -2, -1, -2, -3, -4

Алгоритам за проналажење подсекције максималне дужине са разликом између суседних елемената као 0 или 1

1. Declare a Map.
2. Set maxValue to 0.
3. Traverse the array starting from i=0 to while i<n (length of the array).
  1. Initialize a variable temp to 0.
  2. Check if Map contains the key as arr[i-1],
    1. If true, then get the value of arr[i-1] and store it to temp.
  3. Check if Map contains the key as arr[i],
    1. If true, then find the greater between the temp and the value of arr[i] in the map, and store it to temp.
  4. Check if Map contains the key as arr[i+1],
    1. If true, then find the greater between the temp and the value of arr[i+1] in the map, and store it to temp.
  5. Check if the temp is greater than maxValue,
    1. If true then store the value of temp to maxValue.
  6. And put the arr[i] as a key and temp as a value into the map.
4. Return maxValue.

Објашњење

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

Размотримо пример и схватимо ово:

Пример

Арр [] = {1, 4, 5, 2, 6, 5, 4, 8}

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

и = 0, арр [и] = 1, темп = 0, макВалуе = 0 Мапа = {}

Проверите који ће услов испунити. У овом случају нема услова. Дакле, ради темп ++ и проверава да ли је темп већи од макВалуе. Ако је тачно, сачувајте темп у макВалуе и уметните вредност и темп у мапу.

и = 1, арр [и] = 4, темп = 0, макВалуе = 1.

Мапа = {1,1}

Као и горе наведени услови, ми само убацујемо вредности у мапу

и = 2, арр [и] = 5, темп = 0, макВалуе = 1.

Мапа = {1: 1, 4: 1}

Овог пута налазимо да је први услов тачан да карта садржи арр [и] -1 који је 4. Дакле, 1 узима као темп и ради темп ++. Затим промените макВалуе у 2 и уметните арр [и] и темп у њега.

И једноставно овако, наставићемо да проверавамо услове и узимамо вредности у темп. Наставите да је убацујете у мапу, напокон добијамо вредност у макВалуе као наш излаз.

Подсеквенца максималне дужине са разликом између суседних елемената као 0 или 1

код

Ц ++ код за проналажење подсекције максималне дужине са разликом између суседних елемената као 0 или 1

#include<iostream>
#include<unordered_map>

using namespace std;

int getMaximumLenSubsequence(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int maxValue = 0;
    for (int i=0; i<n; i++)
    {
        int temp = 0;
        if (MAP.find(arr[i]-1) != MAP.end() && temp < MAP[arr[i]-1])
            temp = MAP[arr[i]-1];

        if (MAP.find(arr[i]) != MAP.end() && temp < MAP[arr[i]])
            temp = MAP[arr[i]];

        if (MAP.find(arr[i]+1) != MAP.end() && temp < MAP[arr[i]+1])
            temp = MAP[arr[i]+1];

        MAP[arr[i]] = temp + 1;

        if (maxValue < MAP[arr[i]])
            maxValue = MAP[arr[i]];
    }
    return maxValue;
}
int main()
{
    int arr[] = {1, 4, 5, 2, 6, 5, 4, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getMaximumLenSubsequence(arr, n);
    return 0;
}
5

Јава код за проналажење подсекције максималне дужине са разликом између суседних елемената као 0 или 1

import java.util.HashMap;

class subsequenceLength
{
    public static int getMaximumLenSubsequence(int[] arr)
    {
        int maxValue = 0;
        HashMap<Integer, Integer> MAP = new HashMap<>();
        for (int i = 0; i < arr.length; i++)
        {
            int temp = 0;
            if (MAP.containsKey(arr[i] - 1))
            {
                temp = MAP.get(arr[i] - 1);
            }

            if (MAP.containsKey(arr[i]))
            {
                temp = Math.max(temp, MAP.get(arr[i]));
            }

            if (MAP.containsKey(arr[i] + 1))
            {
                temp = Math.max(temp, MAP.get(arr[i] + 1));
            }
            temp++;
            if (temp > maxValue)
            {
                maxValue = temp;
            }
            MAP.put(arr[i], temp);
        }
        return maxValue;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 5, 2, 6, 5, 4, 8};
        System.out.println(getMaximumLenSubsequence(arr));
    }
}
5

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

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

Он) где „Н“ је број елемената у низу. Једноставно смо прешли преко свих елемената у низу. Будући да смо користили ХасхМап, могли смо то да урадимо у линеарној временској сложености.

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

Он) где „Н“ је број елемената у низу. Будући да на мапи чувамо податке који се односе на елементе, сложеност простора је такође линеарна.