အရှည်ဆုံးတိုးမြှင့်ဆက်တိုက်နောက်ဆက်တွဲ


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အမေဇုံ Google Microsoft က
အခင်းအကျင်း Dynamic Programming

နောက်ဆက်တွဲများသည်အင်တာဗျူးသူများနှစ်သက်သောအခြားအကြောင်းအရာဖြစ်သည်။ သူတို့ကိုပတ်ပတ်လည်ညှိနှိုင်းသူတို့ကိုအမြဲတမ်းကိုယ်စားလှယ်လောင်းများစမ်းသပ်အသစ်အခွင့်အလမ်းများကိုပေးနိုင်ပါသည်။ ၎င်းသည်လျှောက်ထားသူအားအရာရာကိုစဉ်းစားသုံးသပ်နိုင်သည့်စွမ်းရည်ကိုစစ်ဆေးပြီးအကောင်းဆုံးနှင့်အကောင်းဆုံးဖြေရှင်းချက်များထွက်ပေါ်လာနိုင်သည်။ ယနေ့တွင်ကျွန်ုပ်တို့သည်တူညီသော“ အရှည်ဆုံးတိုးမြှင့်ဆက်တိုက်ဆက်တိုက်နောက်ဆက်တွဲများ” ကိုလုပ်ဆောင်နေကြမည့်နောက်ဆက်တွဲပြproblemနာကိုဖြေရှင်းနေကြသည်။

ပြProbleနာဖော်ပြချက်

ပထမ ဦး စွာပြtheနာကိုဖော်ပြရန်ဘာကိုကြည့်ကြကုန်အံ့။ ကျနော်တို့ကိန်းတစ်ခုခင်းကျင်းပေးထားသည်။ ဒီခင်းကျင်းမှုသည်အမျိုးအစားခွဲခြားထားသည်။ ကျွန်တော်တို့ရဲ့တာဝန်ကတိုးပွားလာနေတဲ့အကြီးမားဆုံးအစိတ်အပိုင်းကိုရှာဖွေဖို့ဖြစ်တယ်။ စည်းမျဉ်းအရဤကိန်းများအကြားတစ်ခုနှင့်တစ်ခုကွာခြားသင့်ကြောင်းဖော်ပြသည်။

နမူနာ

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 မှ DP အထိဤပြproblemနာကိုဖြေရှင်းရန်နည်းလမ်းများစွာရှိသည်။ ထိုကဲ့သို့သောမေးခွန်းများမေးသည့်အခါတိုင်းပိုမိုလွယ်ကူသောလမ်းကိုဖြတ်ပြီး Brute Force သို့သွားရောက်လေ့ရှိသည်။ ဒါပေမယ့်စိတ်မပူပါနဲ့ အကောင်းဆုံးဖြေရှင်းနည်းနဲ့အရှက်ရစေဖို့ဒီကိုငါရောက်လာတယ်။

  • ပထမ ဦး စွာကျွန်ုပ်တို့သည်ဖန်တီးသည် HashMap
  • ဤ HashMap သည်ကျွန်ုပ်တို့ရရှိသောနောက်ဆက်တွဲအရှည်ကိုသိုလှောင်ထားသည်
  • ဤ HashMap ရှိသော့သည်နံပါတ်ဖြစ်သည်။
  • တန်ဖိုးသည်သူနှင့်သက်ဆိုင်သောနောက်ဆက်တွဲအရှည်ဖြစ်သည်။
  • ဒုတိယအားဖြင့်၊
  • arr [i] -1 ကိုစစ်ဆေးသည်။
  • အကယ်၍ HashMap တွင်သော့ရှိလျှင်ကျွန်ုပ်တို့သည်နောက်ဆက်တွဲသို့ထည့်ပါ
  • ငါတို့အဆင်ပြေရန်နှင့်နေရာလွတ်သိုလှောင်ရန်အတွက်ယခင်သော့ကိုဖျက်ပစ်နိုင်သည်
  • HashMap မှာကီးမရှိဘူးဆိုရင်
  • 1 ကိုလက်ရှိဒြပ်စင်၏သော့အဖြစ်ထည့်ပါ
  • နောက်ဆုံးအနေဖြင့်ကျွန်ုပ်တို့သည်အရှည်အားလုံး၏အများဆုံးကိုတွေ့နိုင်သည်
  • ထို့ကြောင့်ကျွန်ုပ်တို့သည်ယခုတွင် LICS ရှိသည်!

ကုဒ်

အခုငါတို့ဒီပြproblemနာကိုဘယ်လိုဖြေရှင်းကြလဲဆိုတာနားလည်ပြီ။ ပထမ ဦး စွာကျွန်ုပ်တို့၏အတွေးအခေါ်များကို Java Code ဖြင့်ကုဒ်သွင်းပါရစေ။

အရှည်ဆုံးတိုး။ ဆက်တိုက်ဆက်တိုက်အရှည်ကိုရှာရန် Java Code

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 သို့ပြောင်းနေသည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်အကူးအပြောင်းသို့ရောက်နေပြီဖြစ်သည် unordered မြေပုံများ မှ 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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေးမှု = အို (N)

  • array တစ်ခုလုံးကိုဖြတ်သန်းပါတယ်
  • ကျနော်တို့ကတစ်ကြိမ်မှာဒြပ်စင်တစ်ခုစဉ်းစားနေကြသည်
  • ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုသည်အို (N) ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု = အို (N)

  • ကျနော်တို့သော့ကိုနံပါတ်များအဖြစ်ချပြီးနေကြသည်
  • သော့များကိုဖယ်ရှားခြင်းပင်လျှင်အကောင်းဆုံးကိစ္စတွင်သော့တစ်ချောင်းသာရှိသည်
  • ဒါပေမယ့်ပိုဆိုးတာကတော့ element တွေအားလုံးကို HashMap မှာပေါင်းထည့်လိုက်တာပဲ
  • ၎င်းသည် O (N) ၏နေရာရှုပ်ထွေးမှုကိုဖြစ်ပေါ်စေသည်။