Последователна максимална должина со разлика помеѓу соседните елементи или 0 или 1


Ниво на тешкотија Медиум
Често прашувано во Cisco Expedia Qualtrics SAP лаборатории Teradata
Низа Динамичко програмирање

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

Ти е даден број низа. Проблемот „Последователна максимална должина со разлика помеѓу соседните елементи како 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. За да го решиме ова, ќе користиме хашинг да го направиме нашето решение ефикасно. Toе го ставиме клучот како елемент на низата и ќе ја земеме вредноста на клучот секогаш наоѓајќи ја максималната вредност и зачувајте ја во темб.

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

пример

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

Првото нешто што го правиме е да прогласиме за мапа затоа што ќе зачуваме низа елемент и временски вредности според алгоритмот за кој разговаравме. Поставете ја вредноста на maxValue на 0. thisе ја вратиме оваа променлива. Што е во таа променлива, би бил нашиот одговор. Traе ја поминеме низата и ќе ја натераме да ја достигне должината на низата. Секојпат кога ќе ја пресечеме низата со новата вредност на i, иницијализираме временска вредност на 0.

i = 0, arr [i] = 1, temp = 0, maxValue = 0 Мапа = {}

Проверете кој услов ќе се исполни. Во овој случај, нема услов. Значи, тоа прави temp ++ и проверува дали temp е поголем од maxValue. Ако е точно, складирајте го температурниот режим во maxValue и вметнете ја вредноста и температурата на картата.

i = 1, arr [i] = 4, temp = 0, maxValue = 1.

Мапа = {1,1}

Исто како и горенаведениот услов, ние само ги вметнуваме вредностите во мапата

i = 2, arr [i] = 5, temp = 0, maxValue = 1.

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

Овој пат го наоѓаме точниот прв услов дека мапата содржи arr [i] -1, што е 4. Значи, го зема 1-от како temp и направи temp ++. Потоа, променете ја максималната вредност на 2 и внесете arr [i] и темпо во неа.

И едноставно вака, ние ќе продолжиме да ги проверуваме условите и да ги земаме вредностите во температурата. Продолжете да го вметнувате на мапа, конечно, ја добиваме вредноста во maxValue како излез.

Последователна максимална должина со разлика помеѓу соседните елементи или 0 или 1

Код

C ++ код за да се најде последователноста на максималната должина со разлика помеѓу соседните елементи или 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

Java код за да се најде последователноста на максималната должина со разлика помеѓу соседните елементи или 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

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

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

Тој) каде „Н“ е бројот на елементи во низата. Ние едноставно ги преминавме сите елементи во низата. Бидејќи користевме HashMap, бевме во можност да го сториме тоа во линеарно време на сложеност.

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

Тој) каде „Н“ е бројот на елементи во низата. Бидејќи чуваме податоци поврзани со елементи на картата, комплексноста на просторот е исто така линеарна.