Најдуже све веће узастопно следовање


Ниво тешкоће Лако
Често питани у амазонка гоогле мицрософт
Ред Динамичко програмирање

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

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

Прво погледајмо шта проблем треба да пренесе. Добијамо низ целих бројева. Овај низ није сортиран. Наш задатак је да откријемо највећи подскуп који се повећава. Правило налаже да ови цели бројеви треба да имају једну разлику између њих.

Пример

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

Могући подскупови

6,7

2,3,4,5

9,10

Length of Longest Increasing Subsequence: 4

Као што слика вреди хиљаду речи. Погледајмо слику која то илуструје. Црвени регион на слици приказује прихватљиви подскуп.

Најдуже све веће узастопно следовање

Приступ дужини ЛИЦС

Постоји неколико метода за решавање овог проблема, од грубе силе до ДП. Кад год се поставе таква питања, ми тежимо да кренемо лакшим путем и погледамо у Бруте Форце. Али не брините. Овде сам да вам спасим срамоту најбољим решењем.

  • Прво, креирамо ХасхМап
  • Ова ХасхМап чува дужину подсеквенци које имамо
  • Кључ овог ХасхМап-а је број.
  • Вредност је дужина подсекције која је са њом повезана.
  • Друго, понављамо низ
  • Проверавамо за арр [и] -1.
  • Ако ХасхМап има кључ који додајемо у след
  • Претходни кључ можемо избрисати ради своје удобности и ради складиштења простора
  • Ако ХасхМап нема кључ
  • Додамо 1 као кључ тренутног елемента
  • И на крају, налазимо максимум свих дужина
  • Дакле, сада имамо ЛИЦС!

код

Сад кад смо схватили како се решава овај проблем. Прво ставимо своје идеје у кодирање помоћу Јава кода.

Јава код за проналажење најдуже растуће узастопне дужине следова

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

Како прелазимо са Јаве на Ц ++. Прелазимо са Цоллецтион Фрамеворк на СТЛ. Дакле, прелазимо на неуређене мапе од ХасхМап. Сада када знамо промене, пребацимо језик.

Ц ++ код за проналажење најдуже растуће узастопне дужине следова

#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

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

Сложеност времена = О (Н)

  • Провлачимо се кроз читав низ
  • Разматрамо један по један елемент
  • Дакле, временска сложеност је О (Н)

Сложеност простора = О (Н)

  • Кључеве стављамо као бројеве
  • Чак и када уклањате кључеве, у најбољем случају може постојати само један кључ
  • Међутим, у најгорем случају, могли бисмо на крају додати све елементе у ХасхМап
  • Што доводи до сложености простора О (Н)