పెరుగుతున్న తరువాతి గరిష్ట ఉత్పత్తి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అకోలైట్ GE హెల్త్ HackerRank IBM Snapchat యాహూ
అర్రే డైనమిక్ ప్రోగ్రామింగ్

సమస్యల నివేదిక

“పెరుగుతున్న తరువాతి గరిష్ట ఉత్పత్తి” సమస్య మీకు పూర్ణాంకాల శ్రేణిని ఇస్తుందని పేర్కొంది. ఇప్పుడు మీరు సాధించగల గరిష్ట ఉత్పత్తిని తెలుసుకోవాలి, పెరుగుతున్న తరువాతి మూలకాలను మీరు గుణించాలి. గమనించదగ్గ విషయం ఏమిటంటే, ఎక్కువ కాలం పెరుగుతున్న తరువాతి పరిణామాలను మనం కనుగొనడం లేదు. మనకు చిన్న పరిణామం ఉండవచ్చు కానీ అది గరిష్ట ఉత్పత్తిని కలిగి ఉండాలి.

ఉదాహరణ

పెరుగుతున్న తరువాతి గరిష్ట ఉత్పత్తి

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

పెరుగుతున్న తరువాతి గరిష్ట ఉత్పత్తి 10, 1000. ఎక్కువ కాలం పెరుగుతున్న తరువాతి {1, 2, 3, 4 is అయినప్పటికీ.

అప్రోచ్

సమస్య పోలి ఉంటుంది పొడవైన పెరుగుతున్న పరిణామం సమస్య. ఆ సమస్యపై స్వల్ప మార్పు ఏమిటంటే, ఎక్కువ కాలం పెరుగుతున్న తదుపరిదాన్ని కనుగొనటానికి బదులుగా. పెరుగుతున్న తరువాతి గరిష్ట ఉత్పత్తిని మనం కనుగొనాలి.

కాబట్టి, ఈ సమస్యను పరిష్కరించడానికి. సమస్యను పరిష్కరించడానికి మేము బ్రూట్ ఫోర్స్ అప్రోచ్‌ను ఉపయోగించవచ్చు. ఈ పద్ధతి అసమర్థంగా ఉన్నప్పటికీ తెలుసుకోవాలి. కాబట్టి, బ్రూట్ ఫోర్స్ విధానంలో, మేము మొదట అన్ని తదుపరి పరిణామాలను ఉత్పత్తి చేస్తాము. తరువాతి పరిణామాలను సృష్టించిన తరువాత, మేము చెకర్ ఫంక్షన్‌ను సృష్టిస్తాము. చెకర్ ఫంక్షన్లో, తరువాతి చెల్లుబాటు అవుతుందో లేదో మేము తనిఖీ చేస్తాము. చెకర్ ఫంక్షన్ యొక్క ప్రామాణికత అంటే, తరువాతి కాలం పెరుగుతున్న తరువాతిదిగా ఉండాలి. ఆ తరువాత, పెరుగుతున్న తరువాతి నుండి కనుగొనబడిన గరిష్ట ఉత్పత్తిని మేము నవీకరిస్తూనే ఉన్నాము.

ఇప్పుడు ప్రశ్న ఏమిటంటే మేము సమస్యను సమర్థవంతంగా ఎలా పరిష్కరించగలం? సమస్యను సమర్థవంతంగా పరిష్కరించడానికి, మేము డైనమిక్ ప్రోగ్రామింగ్‌ను ఉపయోగిస్తాము. సమస్యలో పరివర్తన LIS సమస్య వలె ఉంటుంది. ప్రస్తుత మూలకం వరకు మేము అన్ని అంశాలను పరిగణనలోకి తీసుకుంటే పొందగలిగే గరిష్ట ఉత్పత్తిని మా డిపి శ్రేణి నిల్వ చేస్తుంది. మరియు తరువాతి స్థితిలో ప్రస్తుత మూలకం ఉండాలి అని మరో షరతు ఉంది. అప్పుడు DP శ్రేణిని లెక్కించడానికి మేము ప్రస్తుత మూలకం నుండి ప్రారంభ మూలకం వరకు వెనుకబడిన దిశలో సమూహ లూప్‌ను నడుపుతాము. ప్రస్తుత మూలకం కంటే చిన్నదిగా ఉన్న ఒక మూలకాన్ని మేము కనుగొంటే, ప్రస్తుత మూలకాన్ని DP శ్రేణిలోని ఆ సూచికలోని మూలకానికి గుణించడం ప్రస్తుతం నిల్వ చేసిన విలువ కంటే ఎక్కువగా ఉంటే మన జవాబును నవీకరిస్తాము.

కోడ్

పెరుగుతున్న తరువాతి గరిష్ట ఉత్పత్తిని కనుగొనడానికి సి ++ కోడ్

#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 పట్టికను సృష్టిస్తాము. అందువలన స్థల సంక్లిష్టత సరళంగా ఉంటుంది.