တစ်ခုတိုးပွားလာနောက်ဆက်တွဲ၏အများဆုံးထုတ်ကုန်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Accolite GE Healthcare HackerRank IBM က Snapchat Yahoo က
အခင်းအကျင်း Dynamic Programming

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

ပြanနာ“ အများဆုံးတိုးလာသည့်နောက်ဆက်တွဲအကျိုးဆက်” သည်သင့်အားကိန်းဂဏန်းများစွာပေးထားကြောင်းဖော်ပြသည်။ ယခုသင်ရရှိနိုင်သောအမြင့်ဆုံးထုတ်ကုန်ကိုရှာဖွေရန်လိုအပ်ပြီးတိုးပွားလာသောနောက်ဆက်တွဲ၏အစိတ်အပိုင်းများကိုများပြားစေသည်။ မှတ်သားရမည့်အချက်မှာကျွန်ုပ်တို့သည်အရှည်ဆုံးတိုးပွားမှုနောက်ဆက်တွဲကိုရှာဖွေရန်မရည်ရွယ်ပါ။ ကျွန်ုပ်တို့တွင်နောက်ဆက်တွဲသေးငယ်မှုရှိနိုင်သော်လည်းအများဆုံးထုတ်ကုန်ရှိသင့်သည်။

နမူနာ

တစ်ခုတိုးပွားလာနောက်ဆက်တွဲ၏အများဆုံးထုတ်ကုန်

10, 1, 1000, 2, 3, 4
10000

တိုးပွားလာသောနောက်ဆက်တွဲအကျိုးဆက်၏အများဆုံးထုတ်ကုန်မှာ ၁၀၊ ၁၀၀ ဖြစ်သည်။ အရှည်ဆုံးတိုးခြင်း {10, 1000, 1, 2} ဖြစ်သော်လည်း

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

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

ဒီတော့ဒီပြproblemနာကိုဖြေရှင်းဖို့။ ပြtheနာကိုဖြေရှင်းရန် Brute Force Approach ကိုကျွန်ုပ်တို့အသုံးပြုနိုင်သည်။ ဤနည်းလမ်းသည်မတတ်နိုင်သော်လည်းသိသင့်သည်။ ထို့ကြောင့် brute force ချဉ်းကပ်မှုတွင်ပထမ ဦး ဆုံးဖြစ်ပေါ်လာမည့်အကျိုးဆက်များကိုကျွန်ုပ်တို့ပထမဆုံးထုတ်ယူလိမ့်မည်။ နောက်ဆက်တွဲများကိုထုတ်လုပ်ပြီးနောက်ကျွန်ုပ်တို့သည် Checker လုပ်ဆောင်ချက်တစ်ခုကိုဖန်တီးသည်။ Checker လုပ်ဆောင်ချက်တွင်နောက်ဆက်တွဲသည်မှန်မမှန်စစ်ဆေးသည်။ Checker လုပ်ဆောင်ချက်၏တရားဝင်မှုသည်နောက်ဆက်တွဲအကျိုးဆက်များသည်တိုးပွားလာသောနောက်ဆက်တွဲဖြစ်သင့်သည်ကိုဆိုလိုသည်။ ထို့နောက်ကျွန်ုပ်တို့သည်တိုးပွားလာသောနောက်ဆက်တွဲမှတွေ့ရှိသည့်အများဆုံးထုတ်ကုန်ကို ဆက်၍ မွမ်းမံကြသည်။

ပြtheနာကိုဘယ်လိုထိထိရောက်ရောက်ဘယ်လိုဖြေရှင်းနိုင်မလဲဆိုတဲ့မေးခွန်းပါ။ ပြtheနာကိုထိရောက်စွာဖြေရှင်းနိုင်ရန်ကျွန်ုပ်တို့သည် Dynamic Programming ကိုအသုံးပြုသည်။ ပြtheနာ၏အကူးအပြောင်းသည် LIS ပြproblemနာနှင့်အတူတူပင်ဖြစ်သည်။ ကျွန်ုပ်တို့၏ DP ခင်းကျင်းမှုသည်အမြင့်ဆုံးသောကုန်ပစ္စည်းကိုသိုလှောင်ထားသည်။ နောက်ဆက်တွဲတစ်ခုမှာလက်ရှိဒြပ်စင်ပါ ၀ င်သင့်သည့်နောက်ထပ်အခြေအနေတစ်ခုရှိသေးသည်။ ထို့နောက် DP ခင်းကျင်းမှုကိုတွက်ချက်ရန်အတွက်ကျွန်ုပ်တို့က nested loop တစ်ခုကိုလက်ရှိ element မှစတင်သည့် element သို့နောက်သို့ ဦး တည်သွားစေသည်။ အကယ်၍ ကျွန်ုပ်တို့သည်လက်ရှိ element ထက်သေးငယ်သော element တစ်ခုကိုတွေ့ရှိပါက DP ခင်းကျင်းမှုရှိထိုအညွှန်းကိန်းရှိ element ကိုလက်ရှိ element ကိုမြှောက်ခြင်းသည်လက်ရှိသိုလှောင်ထားသည့်တန်ဖိုးထက်သာလွန်ပါကကျွန်ုပ်တို့၏အဖြေကိုကျွန်ုပ်တို့ပြောင်းလဲနိုင်သည်။

ကုဒ်

တိုးမြှင့်နောက်ဆက်တွဲ၏အများဆုံးထုတ်ကုန်ကိုရှာဖွေ C ++ ကုဒ်

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


int maxProductOfIncreasingSubsequence(vector<int> &input){
  vector<int> dp(n);
  dp[0] = input[0];
  int ans = input[0];
  for(int i=1;i<n;i++){
    for(int j=0;j<i;j++){
      if(input[j] < input[i])
        dp[i] = max(dp[i], dp[j]*input[i]);
    }
    ans = max(ans, dp[i]);
  }
  return ans;
}

int main(){
  int n;cin>>n;
  vector<int> input(n);
  for(int i=0;i<n;i++)
    cin>>input[i];

  cout<<maxProductOfIncreasingSubsequence(input);
}
6
10 1 1000 2 3 4
10000

တိုးမြှင့်နောက်ဆက်တွဲ၏အများဆုံးထုတ်ကုန်ကိုရှာဖွေဂျာဗားကုဒ်

import java.util.*;

class Main{
    static int maxProductOfIncreasingSubsequence(ArrayList<Integer> input){
    ArrayList<Integer> dp = new ArrayList<Integer>();
    dp.add(input.get(0));
    int ans = input.get(0);
    int n = input.size();
    for(int i=1;i<n;i++){
      dp.add(input.get(i));
      for(int j=0;j<i;j++){
        if(input.get(j) < input.get(i))
          dp.set(i, Math.max(dp.get(i), dp.get(j)*input.get(i)));
      }
      ans = Math.max(ans, dp.get(i));
    }
    return ans;
  }

  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    ArrayList<Integer> input = new ArrayList<>();
    for(int i=0;i<n;i++){
      int in = sc.nextInt();
      input.add(in);
    }

    int answer = maxProductOfIncreasingSubsequence(input);
    System.out.print(answer);
  }
}
6
10 1 1000 2 3 4
10000

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

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

အို (N ^ 2) သည်ကျွန်ုပ်တို့အသိုက်ကွင်းနှစ်ခုကိုအသုံးပြုနေသောကြောင့်ဖြစ်သည်။ element တွေအားလုံးကိုဖြတ်သွားတဲ့နောက်တစ်ခုကအတွင်းပိုင်း loop က element တွေအားလုံးကို current element အထိရောက်အောင် run တယ်။

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

အို (N) သည်ကျွန်ုပ်တို့သည်တစ်ခုတည်းသော DP ဇယားကိုဖန်တီးသောကြောင့်ဖြစ်သည်။ ထို့ကြောင့်အာကာသရှုပ်ထွေး linear ဖြစ်ပါတယ်။