တိကျတဲ့ခြားနားချက်နှင့်အတူအားလုံးအတွက်အများဆုံးပေါင်းလဒ်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Accolite Coursera ဒေလီ လေးကစ် Snapdeal
အခင်းအကျင်း Dynamic Programming

ပြspecificနာက“ တိကျတဲ့ကွဲပြားခြားနားမှုရှိသောအများဆုံးအရေအတွက်” ကသင့်ကို array တစ်ခုပေးထားတယ်ဆိုတာဖော်ပြတယ် ကိန်း နှင့်ကိန်းပြည့်ကိန်းတစ်ခုဖြစ်လျှင်လွတ်လပ်သောအားလုံးအတွက်အများဆုံးပေါင်းလဒ်ကိုရှာရန်ကျွန်ုပ်တို့အားတောင်းဆိုသည်။ သူတို့မှာလုံးဝခြားနားတဲ့ K. ထက်နည်းရင် ၂ လုံးကိန်းနှစ်ခုကိုတွဲနိုင်တယ်။

နမူနာ

တိကျတဲ့ခြားနားချက်နှင့်အတူအားလုံးအတွက်အများဆုံးပေါင်းလဒ်

42, 43, 4, 5, 6, 12
96

ရှင်းလင်းချက်

၄၂၊ ၄၃ နှင့် ၅၊ ၆ တို့ကိုရွေးသည်။ ၄၊ ၅ နှင့် ၆ တို့တွင်ရွေးစရာများရှိခဲ့သည်။ ရလဒ်အနေဖြင့်ရလဒ်အမြင့်ဆုံး = ၉၆ ဖြစ်သည်။

ချဉ်းကပ်နည်း

ပြproblemနာကကျွန်ုပ်တို့၏အချို့သောဒြပ်စင်များကိုတွဲဖက်ပါကရရှိနိုင်သောအမြင့်ဆုံးပမာဏကိုရှာဖွေရန်ဖြစ်သည် အခင်းအကျင်း။ ကျွန်ုပ်တို့သည်ပြelementsနာကိုမဖြေရှင်းခင်၊ ကျွန်ုပ်တို့သည် element များမှအကြွင်းမဲ့ခြားနားချက် K. ထက်နည်းရမည်ဟုသတ်မှတ်ထားသောအခြေအနေအောက်တွင် element များကိုတွဲစပ်နိုင်သည် ကြမ္မာ အဆိုပါခင်းကျင်း။ ဤနည်းဖြင့်ကျွန်ုပ်တို့၏ရှာဖွေရေးနေရာကိုခုတ်လှဲသည်။ ကျွန်တော်တို့မှာ unsorted array ရှိတယ်ဆိုတာစဉ်းစားပါ။ ပြီးရင် element တစ်ခုနဲ့တွဲဖို့ element အားလုံးကိုဖြတ်ရမယ်။ ဒါပေမယ့် sort လုပ်ပြီးတဲ့အခါမှာအကြီးဆုံး element ကသူ့အရင် element ကပဲသိတယ်။ အခြေအနေကကျေနပ်မှုရှိမရှိစစ်ဆေးပါတယ်။

အခြေအနေကိုကျေပွန်လျှင်၊ ကျွန်ုပ်တို့သည်ယခင်နှင့်လက်ရှိဒြပ်စင်ကို တွဲ၍ ပြက္ခဒိန်၏နောက်ဆုံးဒြပ်စင် (လက်ရှိဒြပ်စင်မှ) အထိထည့်သည်။ ဒါပေမယ့်အခြေအနေကကျေနပ်မှုမရှိဘူးဆိုရင်။ ကျနော်တို့တွဲဖက်မှုစွန့်ခွာခြင်းနှင့်ရလဒ်သည်ယခင်ဒြပ်စင်သည်အထိ၏တူညီသည်။ ပိုပြီးတရားဝင်အနေဖြင့်ရလဒ် [i] = ရလဒ် [i-2] + ထည့်သွင်းမှု [i] + input [i-2]၊ အပြန်အလှန်အားပြုပါကရလဒ် [i] = ရလဒ် [i-1] ။ ဒီရလဒ်ဒီ array ကငါတို့ DP ကျွန်တော်တို့ဟာသေးငယ်တဲ့ subproblems ၏ရလဒ်သိုလှောင်သောကြောင့်။ အောက်ခြေ DP မှာလုပ်သလိုမူလပြproblemနာရဲ့ရလဒ်ကိုရှာရန်ဤသေးငယ်သော subproblems ၏ရလဒ်များကိုပေါင်းစပ်သည်။

ကုဒ်

တိကျတဲ့ခြားနားချက်နှင့်အတူအများဆုံးအများဆုံးပေါင်းလဒ်ကိုရှာဖွေ C ++ ကုဒ်

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int input[] = {42, 43, 4, 5, 6, 12};
    int n = sizeof(input)/sizeof(int);
    int K = 4;
    sort(input, input+n);
    int dp[n];
    memset(dp, 0, sizeof dp);
    for(int i=1;i<n;i++){
        dp[i] = dp[i-1];
        if(input[i]-input[i-1] < K)
            dp[i] = max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
    }
    cout<<dp[n-1];
    return 0;
}
96

တိကျတဲ့ခြားနားချက်နှင့်အတူအများဆုံးအများဆုံးပေါင်းလဒ်ကိုရှာဖွေ Java code ကို

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int input[] = {42, 43, 4, 5, 6, 12};
      int n = input.length;
      int K = 4;
      Arrays.sort(input);
      int dp[] = new int[n];
      dp[0] = 0;
      for(int i=1;i<n;i++){
          dp[i] = dp[i-1];
          if(input[i]-input[i-1] < K)
              dp[i] = Math.max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
      }
    System.out.println(dp[n-1]);
  }
}
96

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

အချိန်ရှုပ်ထွေး 

အို (NlogN), ဘာဖြစ်လို့လဲဆိုတော့ကျနော်တို့က array ကိုအစပိုင်းမှာစီထားတာလေ။ merge sort နှင့်အခြား sorting algorithms များသည် O (NlogN) တွင်ခင်းကျင်းနိုင်သည်။ အကယ်၍ ကျွန်ုပ်တို့အားထည့်သွင်းထားသည့်သွင်းအားစုများထည့်သွင်းပါကအို (N) အချိန်တွင်ပြtheနာကိုဖြေရှင်းနိုင်ပါမည်။

အာကာသရှုပ်ထွေးမှု

အို (N)၊ ဒီအာကာသခင်းကျင်း sorting များအတွက်လိုအပ်ပါသည်။ ကျနော်တို့ DP ခင်းကျင်းမှုမလုပ်ခဲ့ဘူးဆိုရင်တောင်မှ DP table အတွက်တူညီတဲ့ input array ကိုသုံးလိမ့်မယ်ဆိုရင်တောင်။ ဒီအာကာသစခန်းသည်အတူတူပင်ရှုပ်ထွေးနေဆဲဖြစ်ပြီးအဘယ်ကြောင့်ဆိုသော်ထိုနေရာသည်စီရန်အတွက်လိုအပ်သောကြောင့်ဖြစ်သည်။