እየጨመረ የመጣው ከፍተኛ ምርት


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የተከማቸ GE የጤና HackerRank IBM Snapchat ያሁ
ሰልፍ ተለዋዋጭ ፕሮግራም

የችግሩ መግለጫ

ችግሩ “እየጨመረ የመጣው ከፍተኛ ምርት” የሚለው ቁጥር ብዙ ቁጥር እንደሚሰጥዎ ይገልጻል። አሁን እየጨመረ የሚመጣውን ንጥረ ነገር አባዛ ብለው እንዲያሳድጉ ሊያደርጓቸው የሚችሏቸውን ከፍተኛውን ምርት መፈለግ ያስፈልግዎታል ፡፡ ልብ ሊባል የሚገባው ነገር ቢኖር ፣ ረዥሙን እየጨመረ የመጣውን ተከታይ ለማወቅ አይጠበቅብንም ፡፡ እኛ ትንሽ ተከታይ ሊኖረን ይችላል ግን ከፍተኛው ምርት ሊኖረው ይገባል ፡፡

ለምሳሌ

እየጨመረ የመጣው ከፍተኛ ምርት

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

እየጨመረ የሚሄድ ከፍተኛው ምርት 10 ፣ 1000 ነው። ምንም እንኳን ረዥሙ እየጨመረ ያለው ቀጣይነት ግን {1, 2, 3, 4} ቢሆንም።

ቀረበ

ችግሩ ከሱ ጋር ይመሳሰላል ረጅሙ እየጨመረ የሚሄድ ውጤት ችግር በዚያ ችግር ላይ ያለው ትንሽ ማሻሻያ ረጅሙን እየጨመረ የመጣውን ቀጣይ ፍለጋ ከማግኘት ይልቅ ነው ፡፡ እየጨመረ የሚመጣውን ከፍተኛ ምርት ማግኘት አለብን።

ስለዚህ ይህንን ችግር ለመፍታት ፡፡ እኛም እንዲሁ ችግሩን ለመፍታት Brute Force Approach ን ልንጠቀም እንችላለን ፡፡ ምንም እንኳን ይህ ዘዴ ውጤታማ ያልሆነ ቢሆንም መታወቅ አለበት ፡፡ ስለዚህ በጭካኔ ኃይል አቀራረብ በመጀመሪያ ሁሉንም ተከታይ እናመነጫለን ፡፡ ተከታዮቹን ከፈጠርን በኋላ የቼክ ተግባር እንፈጥራለን ፡፡ በቼክ ተግባር ውስጥ ፣ ተከታይነቱ ትክክል መሆኑን እንፈትሻለን ፡፡ የአመልካች ተግባር ትክክለኛነት ተከታይ እየጨመረ የሚሄድ መሆን አለበት ማለት ነው ፡፡ ከዚያ በኋላ እየጨመረ ከሚመጣው ውጤት የተገኘውን ከፍተኛውን ምርት ማዘመኑን እንቀጥላለን።

አሁን ጥያቄው ችግሩን በብቃት እንዴት እንፈታዋለን የሚል ነው ፡፡ ችግሩን በብቃት ለመፍታት ፣ ተለዋዋጭ ፕሮግራምን እንጠቀማለን። በችግሩ ውስጥ ያለው ሽግግር ከ 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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (N ^ 2) ምክንያቱም ሁለት የተጠለፉ ቀለበቶችን እየተጠቀምን ስለሆነ ፡፡ አንደኛው በሁሉም ንጥረ ነገሮች ላይ የሚያልፈው እና ሌላኛው የውስጥ ዑደት እስከ አሁን ያለው ንጥረ ነገር ድረስ በሁሉም ንጥረ ነገሮች ላይ ይሠራል።

የቦታ ውስብስብነት

ኦ (ኤን) ምክንያቱም ባለ አንድ ልኬት የዲ ፒ ሰንጠረዥን እንፈጥራለን ፡፡ ስለዚህ የቦታ ውስብስብነት መስመራዊ ነው።