Най-дълго нарастваща последователна последователност


Ниво на трудност Лесно
Често задавани в Амазонка Google Microsoft
Array Динамично програмиране

Последствията са друга тема, обичана от интервюиращите. Променянето им винаги може да им даде нови възможности за тестване на кандидати. Той може да провери способността на кандидата да мисли и анализира нещата и да излезе с най-добрите и оптимални решения. Днес решаваме проблем с подпоследователност, който ще прави същите „Най-дългите нарастващи последователни последователности“.

Декларация за проблема

Първо нека разгледаме какво трябва да предаде проблемът. Даден ни е масив от цели числа. Този масив е несортиран. Нашата задача е да открием най-голямото подмножество, което се увеличава. Правилото гласи, че тези цели числа трябва да имат разлика от едно между тях.

Пример

6, 7, 2, 3, 4, 5, 9, 10

Възможни подмножества

6,7

2,3,4,5

9,10

Length of Longest Increasing Subsequence: 4

Като изображение струва хиляда думи. Нека разгледаме изображение, илюстриращо същото. Червената област на изображението показва допустимата подмножина.

Най-дълго нарастваща последователна последователност

Подход за дължина на LICS

Има няколко метода за решаване на този проблем, вариращи от груба сила до DP. Винаги, когато се задават такива въпроси, ние сме склонни да поемем по-лесния път и да разгледаме Brute Force. Но не се притеснявай. Тук съм, за да ви спестя смущението с най-доброто решение.

  • Първо, ние създаваме a HashMap
  • Тази HashMap съхранява дължината на подпоследователностите, които имаме
  • Ключът в тази HashMap е числото.
  • Стойността е дължината на подпоследователността, свързана с нея.
  • На второ място, итерираме през масива
  • Проверяваме за arr [i] -1.
  • Ако HashMap има ключа, който добавяме към подпоследователността
  • Можем да изтрием предишния ключ за наше удобство и за съхранение на място
  • Ако HashMap няма ключа
  • Добавяме 1 като ключ на текущия елемент
  • И накрая, намираме максимума от цялата дължина
  • По този начин имаме LICS сега!

код

Сега, след като разбрахме как се решава този проблем. Първо нека поставим идеите си за кодиране с Java код.

Java код за намиране на най-дългата нарастваща последователна дължина на последователността

import java.util.*;
public class Main
{
    public static int LICS(int[] arr)
    {
        HashMap<Integer,Integer>hash=new HashMap<Integer,Integer>();
        for(int i=0;i<arr.length;i++)
        {
            if(hash.containsKey(arr[i]-1))
            {
                hash.put(arr[i],hash.get(arr[i]-1)+1);
                hash.remove(arr[i]-1);
            }
            else
                hash.put(arr[i],1);
        }
        return Collections.max(hash.values());
    }
    public static void main(String args[]) 
    { 
        int arr[]={3, 10, 3, 11, 4, 5, 6, 7, 8, 12};
        System.out.println(LICS(arr));
    }
}
3, 10, 3, 11, 4, 5, 6, 7, 8, 12
6

Тъй като преминаваме от Java към C ++. Преминаваме от Collection Framework към STL. По този начин ние преминаваме към неподредени карти от HashMap. Сега, след като знаем промените, нека превключим езика.

Код на C ++ за намиране на най-дългата нарастваща последователна дължина на последователността

#include<bits/stdc++.h>
using namespace std;
int maxs(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}
int LICS(int arr[],int n)
{
    unordered_map<int,int>store;
    int max=-1;
    for(int i=0;i<n;i++)
    {
        if(store.find(arr[i]-1)!=store.end())
        {
            store[arr[i]]=store[arr[i]-1]+1;
        }
        else
            store[arr[i]]=1;
        max=maxs(max,store[arr[i]]);
    }
    return max;
}
int main()
{
    int a[] = { 3, 10, 3, 11, 4, 5, 6, 7, 8, 12 }; 
    int n = sizeof(a) / sizeof(a[0]); 
    cout << LICS(a, n); 
    return 0; 
}
3, 10, 3, 11, 4, 5, 6, 7, 8, 12
6

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

Сложност във времето = O (N)

  • Превключваме през целия масив
  • Обмисляме един елемент в даден момент
  • По този начин сложността във времето е O (N)

Сложност на пространството = O (N)

  • Поставяме ключовете като числа
  • Дори при премахване на ключове, в най-добрия случай може да има само един ключ
  • В по-лошия случай обаче може да добавим всички елементи към HashMap
  • Което води до космическа сложност на O (N)