Најдолго зголемување на последователните последици


Ниво на тешкотија Лесно
Често прашувано во Амазон Google Мајкрософт
Низа Динамичко програмирање

Последиците се друга тема што ја сакаат анкетарите. Свитањето околу нив секогаш може да им даде нови можности за тестирање на кандидати. Може да ја провери способноста на кандидатот да размислува и да анализира работи и да излезе со најдобри и оптимални решенија. Денес решаваме проблем на последователноста што ќе го прави истото „Најдолго зголемување на последователните последици“.

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

Прво, да разгледаме што треба да пренесе проблемот. Дадена низа е цел број. Оваа низа е несортирана. Нашата задача е да ја откриеме најголемата подгрупа која се зголемува. Правилото вели дека овие цели броеви треба да имаат една разлика помеѓу нив.

пример

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

Можни подмножества

6,7

2,3,4,5

9,10

Length of Longest Increasing Subsequence: 4

Како слика вреди илјада зборови. Дозволете ни да погледнеме слика што го илустрира истото. Црвениот регион на сликата го прикажува подобното подмножество.

Најдолго зголемување на последователните последици

Пристап за должината на LICS

Постојат неколку методи за решавање на овој проблем, почнувајќи од брутална сила до ДП. Кога и да се постават вакви прашања, ние треба да одиме полесно по патот и да погледнеме во Brute Force. Но не грижи се. Тука сум за да ви го спасам срамот со најдобро решение.

  • Прво, ние создаваме HashMap
  • Овој HashMap ја складира должината на следниве редови
  • Клучот во овој HashMap е бројот.
  • Вредноста е должината на редоследот поврзан со неа.
  • Второ, ние повторуваме низ низата
  • Проверуваме за arr [i] -1.
  • Ако HashMap го има клучот, го додаваме на следната
  • Можеме да го избришеме претходниот клуч за наша погодност и за складирање на простор
  • Ако HashMap го нема клучот
  • Ние додаваме 1 како клуч на тековниот елемент
  • И на крај, го наоѓаме максимумот од целата должина
  • Така, сега ги имаме ЛИЦЕВИТЕ!

Код

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

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 ++. Ние се префрламе од Рамката за наплата во 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)

Вселенска комплексност = О (Н)

  • Ние ги ставаме клучевите како броеви
  • Дури и при отстранување на клучеви, во најдобар случај, може да има само еден клуч
  • Меѓутоа, во полоша случај, можеби ќе ги додадеме сите елементи на HashMap
  • Што доведува до вселенска сложеност на О (Н)