વધતી જતી અનુગામીનું મહત્તમ ઉત્પાદન


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે ભેગા જીઇ હેલ્થકેર હેકરરંક IBM Snapchat યાહૂ
અરે ડાયનેમિક પ્રોગ્રામિંગ

સમસ્યા નિવેદન

સમસ્યા "વધતી જતી અનુગામીનું મહત્તમ ઉત્પાદન" જણાવે છે કે તમને પૂર્ણાંકોની એરે આપવામાં આવે છે. હવે તમારે મહત્તમ ઉત્પાદન મેળવવાની જરૂર છે જે તમે પ્રાપ્ત કરી શકો કે તમે વધતા સબક્વોન્સના તત્વોને ગુણાકાર કરો. નોંધનીય બાબત એ છે કે, આપણે સૌથી લાંબો વધતા અનુગામી શોધી કા .વાના નથી. આપણી પાસે એક નાનો અનુગામી હોઈ શકે છે પરંતુ તેમાં મહત્તમ ઉત્પાદન હોવું જોઈએ.

ઉદાહરણ

વધતી જતી અનુગામીનું મહત્તમ ઉત્પાદન

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

વધતી જતી અનુગામીનું મહત્તમ ઉત્પાદન 10, 1000 છે. તેમ છતાં, સૌથી લાંબી વધતી અનુગામી {1, 2, 3, 4} છે.

અભિગમ

સમસ્યા જેવું લાગે છે લાંબી વધતી જતી ઉપગતિ સમસ્યા. તે સમસ્યા પર થોડો ફેરફાર એ છે કે તેની જગ્યાએ સૌથી વધુ વધતા અનુગામીને શોધવા. આપણે વધતા જતા અનુગામીનું મહત્તમ ઉત્પાદન શોધવાની જરૂર છે.

તેથી, આ સમસ્યા હલ કરવા માટે. સમસ્યાને હલ કરવા માટે આપણે બ્રુટ ફોર્સ એપ્રોચનો ઉપયોગ કરી શકીએ છીએ. તેમ છતાં આ પદ્ધતિ બિનકાર્યક્ષમ છે પરંતુ તે જાણવી જોઈએ. તેથી, બ્રુટ ફોર્સ અભિગમમાં, આપણે સૌ પ્રથમ સબકencesન્સિસ બનાવીશું. સબકencesન્સિસ બનાવ્યા પછી, અમે એક ચેકર ફંક્શન બનાવીએ છીએ. તપાસનાર કાર્યમાં, અમે તપાસો કે અનુગામી માન્ય છે કે નહીં. પરીક્ષક કાર્યની માન્યતાનો અર્થ એ છે કે અનુગામી વધતી જતી અનુગામી હોવી જોઈએ. તે પછી, આપણે વધતા સબક્વેન્સમાંથી મળેલા મહત્તમ ઉત્પાદનને અપડેટ કરવાનું ચાલુ રાખીએ છીએ.

હવે સવાલ એ છે કે આપણે સમસ્યાને અસરકારક રીતે કેવી રીતે હલ કરી શકીએ? સમસ્યાને અસરકારક રીતે હલ કરવા માટે, અમે ડાયનેમિક પ્રોગ્રામિંગનો ઉપયોગ કરીએ છીએ. સમસ્યામાં સંક્રમણ એ એલઆઈએસ સમસ્યા જેવું જ છે. અમારું ડીપી એરે મહત્તમ ઉત્પાદનને સંગ્રહિત કરે છે જે પ્રાપ્ત થઈ શકે છે જો આપણે વર્તમાન તત્વ સુધી બધા તત્વો ધ્યાનમાં લઈશું. અને એક વધુ શરત છે કે અનુગામીમાં વર્તમાન તત્વ હોવું જોઈએ. પછી ડીપી એરેની ગણતરી કરવા માટે આપણે વર્તમાન તત્વથી પ્રારંભિક તત્વ તરફની પછાત દિશામાં નેસ્ડ લૂપ ચલાવીએ છીએ. જો અમને કોઈ તત્વ જોવા મળે છે જે વર્તમાન તત્વ કરતાં નાનું હોય છે, તો અમે ડીપી એરેમાં તે અનુક્રમણિકાના તત્વમાં વર્તમાન તત્વને ગુણાકાર કરીએ તો અમે અમારા જવાબોને અપડેટ કરીએ છીએ તે હાલમાં સંગ્રહિત મૂલ્ય કરતા વધારે છે.

કોડ

વધતી અનુગામીના મહત્તમ ઉત્પાદનને શોધવા માટે સી ++ કોડ

#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) કારણ કે અમે બે નેસ્ડ લૂપ્સનો ઉપયોગ કરી રહ્યાં છીએ. એક જે તમામ તત્વો ઉપર ચાલે છે અને અન્ય આંતરિક લૂપ વર્તમાન તત્વ સુધી બધા તત્વો ઉપર ચાલે છે.

અવકાશ જટિલતા

ઓ (એન) કારણ કે અમે એક-પરિમાણીય ડીપી ટેબલ બનાવીએ છીએ. આમ જગ્યા જટિલતા રેખીય છે.