एक बढ़ती हुई क्षमता का अधिकतम उत्पाद


कठिनाई स्तर आसान
में अक्सर पूछा एकोलाइट जीई हेल्थकेयर HackerRank आईबीएम Snapchat याहू
ऐरे गतिशील प्रोग्रामिंग

समस्या का विवरण

समस्या "एक बढ़ती हुई स्थिति के अधिकतम उत्पाद" में कहा गया है कि आपको एक पूर्णांक दिया जाता है। अब आपको अधिकतम उत्पाद प्राप्त करने की आवश्यकता है जो आप इस तरह प्राप्त कर सकते हैं कि आप एक बढ़ते क्रम के तत्वों को गुणा करें। ध्यान देने वाली बात यह है कि, हमें सबसे लंबे समय तक बढ़ने वाले परिणाम का पता नहीं लगाना चाहिए। हमारे पास एक छोटी सी अनुवर्तीता हो सकती है लेकिन इसमें अधिकतम उत्पाद होना चाहिए।

उदाहरण

एक बढ़ती हुई क्षमता का अधिकतम उत्पाद

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

एक बढ़ती हुई अनुवर्तीता का अधिकतम उत्पाद 10, 1000 है। भले ही सबसे लंबे समय तक वृद्धि की स्थिति {1, 2, 3, 4} है।

दृष्टिकोण

समस्या जैसा दिखता है सबसे लंबे समय तक बढ़ते परिणाम संकट। उस समस्या के बारे में थोड़ा संशोधन यह है कि इसके बजाय सबसे लंबे समय तक बढ़ते रहने का पता लगाएं। हमें बढ़ती हुई क्षमता के अधिकतम उत्पाद को खोजने की आवश्यकता है।

तो, इस समस्या को हल करने के लिए। हम समस्या को हल करने के लिए Brute Force दृष्टिकोण का उपयोग कर सकते हैं। भले ही यह तरीका अक्षम हो लेकिन पता होना चाहिए। तो, जानवर बल दृष्टिकोण में, हम पहले सभी बाद उत्पन्न करेंगे। बाद के उत्पन्न करने के बाद, हम एक चेकर फ़ंक्शन बनाते हैं। चेकर फ़ंक्शन में, हम जांचते हैं कि क्या परिणाम वैध है। चेकर फ़ंक्शन की वैधता का मतलब है कि पार्श्वता एक बढ़ती हुई होनी चाहिए। उसके बाद, हम बढ़ते हुए परिणाम से प्राप्त अधिकतम उत्पाद को अपडेट करते रहते हैं।

अब सवाल यह है कि हम समस्या को कुशलता से कैसे हल करें? समस्या को कुशलता से हल करने के लिए, हम डायनेमिक प्रोग्रामिंग का उपयोग करते हैं। समस्या में संक्रमण LIS समस्या के समान है। हमारा डीपी सरणी अधिकतम उत्पाद को संग्रहीत करता है जिसे प्राप्त किया जा सकता है यदि हम वर्तमान तत्व तक सभी तत्वों पर विचार करते हैं। और एक और शर्त है कि बाद में वर्तमान तत्व शामिल होना चाहिए। फिर डीपी सरणी की गणना के लिए, हम वर्तमान तत्व से प्रारंभिक तत्व तक एक पिछड़े दिशा में नेस्टेड लूप चलाते हैं। यदि हमें ऐसा तत्व मिलता है जो वर्तमान तत्व से छोटा है तो हम अपने उत्तर को अपडेट करते हैं यदि वर्तमान तत्व को उस इंडेक्स में डीपी सरणी में गुणा करना वर्तमान में संग्रहीत मूल्य से अधिक है।

कोड

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

जटिलता विश्लेषण

समय जटिलता

ओ (एन ^ 2) क्योंकि हम दो नेस्टेड छोरों का उपयोग कर रहे हैं। एक जो सभी तत्वों पर चलता है और दूसरा आंतरिक लूप मौजूदा तत्वों तक सभी तत्वों पर चलता है।

अंतरिक्ष जटिलता

O (N) क्योंकि हम एकल-आयामी DP तालिका बनाते हैं। इस प्रकार अंतरिक्ष जटिलता रैखिक है।