بڑھتی ہوئی سبقت کی زیادہ سے زیادہ پیداوار


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے اکٹھا کرنا GE صحت کا خیال ہیکرینک IBM Snapchat یاہو
لڑی متحرک پروگرامنگ

مسئلہ یہ بیان

مسئلہ "بڑھتی ہوئی سبقت کا زیادہ سے زیادہ پروڈکٹ" بتاتا ہے کہ آپ کو انٹیجرز کی ایک صف دی جاتی ہے۔ اب آپ کو زیادہ سے زیادہ پروڈکٹ کا پتہ لگانے کی ضرورت ہے جس کو آپ حاصل کرسکتے ہیں تاکہ آپ بڑھتے ہوئے حصے کے عناصر کو ضرب دیں۔ غور کرنے کی بات یہ ہے کہ ، ہمیں یہ نہیں سمجھا جاتا ہے کہ ہم سب سے طویل بڑھتی ہوئی تقابل کو تلاش کریں گے۔ ہوسکتا ہے کہ ہمارے پاس اس کا چھوٹا سا تناسب ہو لیکن اس میں زیادہ سے زیادہ پروڈکٹ ہونی چاہئے۔

مثال کے طور پر

بڑھتی ہوئی سبقت کی زیادہ سے زیادہ پیداوار

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

بڑھتی ہوئی سبقت کا زیادہ سے زیادہ مصنوع 10 ، 1000 ہے۔ اگرچہ سب سے طویل طولانی تقدیر 1 2 ، 3 ، 4 ، XNUMX} ہے۔

نقطہ نظر

مسئلہ سے ملتا ہے سب سے طویل بڑھتی ہوئی مطابقت مسئلہ۔ اس مسئلے پر معمولی ترمیم یہ ہے کہ اس کی بجائے طویل ترین بڑھتی تقلید کو تلاش کریں۔ ہمیں بڑھتے ہوئے حصے کی زیادہ سے زیادہ مصنوعات تلاش کرنے کی ضرورت ہے۔

لہذا ، اس مسئلے کو حل کرنے کے ل. ہم بھی مسئلے کو حل کرنے کے لئے بروٹ فورس اپروچ استعمال کرسکتے ہیں۔ اگرچہ یہ طریقہ غیر موثر ہے لیکن معلوم ہونا چاہئے۔ لہذا ، بروٹ فورس نقطہ نظر میں ، ہم سب سے پہلے کو پیدا کریں گے۔ مضافات پیدا کرنے کے بعد ، ہم ایک چیکر فنکشن تیار کرتے ہیں۔ چیکر فنکشن میں ، ہم جانچ پڑتال کرتے ہیں کہ کیا نتیجہ آگے ہے؟ چیکر فنکشن کی صداقت کا مطلب یہ ہے کہ پیروی ایک بڑھتی ہوئی تقابل ہونا چاہئے۔ اس کے بعد ، ہم بڑھتے ہوئے تقابل سے پائے جانے والے زیادہ سے زیادہ پروڈکٹ کو اپ ڈیٹ کرتے رہتے ہیں۔

اب سوال یہ ہے کہ ہم اس مسئلے کو موثر طریقے سے کیسے حل کریں گے؟ مسئلے کو موثر طریقے سے حل کرنے کے ل we ، ہم متحرک پروگرامنگ کا استعمال کرتے ہیں۔ مسئلے میں تبدیلی LIS مسئلے کی طرح ہی ہے۔ ہمارا ڈی پی صف زیادہ سے زیادہ پروڈکٹ کو اسٹور کرتا ہے جو حاصل کیا جاسکتا ہے اگر ہم موجودہ عنصر تک تمام عناصر پر غور کریں۔ اور ایک اور بھی شرط ہے کہ اس کے بعد والے عنصر میں حالیہ عنصر ہونا چاہئے۔ پھر ڈی پی صف کا حساب لگانے کے ل the ہم موجودہ عنصر سے شروع کرنے والے عنصر تک پسماندہ سمت میں گھسیٹے ہوئے لوپ چلاتے ہیں۔ اگر ہمیں کوئی عنصر ملتا ہے جو موجودہ عنصر سے چھوٹا ہے تو ہم اپنے جواب کو اپ ڈیٹ کرتے ہیں اگر موجودہ عنصر کو عنصر میں ڈی پی سرنی میں اس انڈیکس میں ضرب دینا موجودہ وقت میں ذخیرہ شدہ قیمت سے زیادہ ہے۔

ضابطے

بڑھتے ہوئے حصے کی زیادہ سے زیادہ مصنوعات تلاش کرنے کے لئے 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) کیونکہ ہم ایک جہتی ڈی پی ٹیبل تیار کرتے ہیں۔ اس طرح خلائی پیچیدگی لکیری ہے۔