د مخ په زیاتیدونکې راتلونکې اعظمي محصول


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي اکولایټ په روبل روغتيا هیکرینک IBM Snapchat د ياهو
پیشه متحرک برنامې

ستونزه بیان

ستونزه "د مخ په زیاتیدونکي راتلونکي اعظمي محصول" ویل کیږي چې تاسو ته دقیقو لړۍ درکول کیږي. اوس تاسو اړتیا لرئ اعظمي محصول ومومئ تاسو کولی شئ داسې لاسته راوړئ چې تاسو د مخ په ډیریدو عنصرونو ضرب کړئ. د یادونې وړ خبره دا ده چې موږ باید د ترټولو اوږد ودې راتلونکی راتلونکی ومومو. موږ ممکن یو کوچنی ضمنی برخه ولرو مګر دا باید اعظمي محصول ولري.

بېلګه

د مخ په زیاتیدونکې راتلونکې اعظمي محصول

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

د مخ په ودې راتلونکی اعظمي محصول 10 ، 1000 دی. پداسې حال کې چې ترټولو اوږد ودې ضمني برخه {1 ، 2 ، 3 ، 4} ده.

او کړنلاره

ستونزه د د اوږدې مودې زیاتیدونکې ضمني کول ستونزه. د دې ستونزې په اړه یو څه لږ تغیر دا دی چې د دې پرځای چې د اوږدې مودې ډیریدو راتلونکی ومومئ. موږ اړتیا لرو چې د مخ په زیاتیدونکي راتلونکي اعظمي محصول ومومئ.

نو ، د دې ستونزې حل کولو لپاره. موږ کولی شو د ستونزې حلولو لپاره د بروټ فورس چلند وکاروو. که څه هم دا میتود غیر فعال دی مګر باید وپیژندل شي. نو ، د وحشي ځواک لید کې ، موږ به لومړی ټول فرعي برخې تولید کړو. د ضمني برخو رامینځته کولو وروسته ، موږ د چیکر فعالیت رامینځته کوو. د چیکر فنکشن کې ، موږ ګورو چې ضمني برخه معتبر ده که نه. د چیکر فنکشن اعتبار پدې معنی دی چې ضمنی برخه باید مخ په زیاتیدونکی ضمیمه وي. له هغې وروسته ، موږ د مخ په زیاتیدونکي برخې څخه موندل شوي د اعظمي محصول تازه کولو ته دوام ورکوو.

اوس پوښتنه دا ده چې موږ څنګه ستونزه په مؤثره توګه حل کړو؟ د موثرې ستونزې حل لپاره ، موږ متحرک برنامې کار کوو. په ستونزه کې لیږد د LIS ستونزې ورته دی. زموږ د DP سرنی اعظمي محصول ذخیره کوي چې ترلاسه کیدی شي که چیرې موږ تر اوسني عنصر پورې ټول عناصر په پام کې ونیسو. او یو بل شرط دی چې ضمني برخه باید اوسني عنصر ولري. بیا د DP صفونو محاسبه کولو لپاره موږ له اوسني عنصر څخه پیل کولو عنصر ته په شاته سمت کې ځړیدلي لاپ چلوو. که موږ یو عنصر ومومو چې له اوسني عنصر څخه کوچنی وي نو بیا موږ خپل ځواب تازه کوو که چیرې د DP سرنی کې دې شاخص کې هغه عنصر ته اوسني عنصر ضرب کړو نو اوس مهال زیرمه شوي ارزښت څخه لوی دی.

کوډ

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

د پیچلتیا تحلیل

د وخت پیچلتیا

O (N ^ 2) ځکه چې موږ دوه ځړول شوي لاپونه کاروو. یو څوک چې د ټولو عناصرو باندې تیریږي او نور داخلي لوپ تر اوسني عنصر پورې د ټولو عناصرو باندې تیریږي.

د ځای پیچلتیا

O (N) ځکه چې موږ د واحد واحد DP میز رامینځته کوو. پدې توګه د ځای پیچلتیا لیکه ده.