الحد الأقصى لمنتج لاحق متزايد  


مستوى الصعوبة سهل
كثيرا ما يطلب في Accolite جنرال إلكتريك للرعاية الصحية HackerRank 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

كود Java للعثور على الحد الأقصى من المنتج من نتيجة لاحقة متزايدة

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 أحادي البعد. وبالتالي فإن تعقيد الفضاء خطي.