একটি বর্ধমান অনুচ্ছেদের সর্বোচ্চ পণ্য


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় সমষ্টি জিই হেলথকেয়ার HackerRank আইবিএম Snapchat নরপশু
বিন্যাস ডায়নামিক প্রোগ্রামিং

সমস্যা বিবৃতি

"ক্রমবর্ধমান অনুগতির সর্বোচ্চ পণ্য" সমস্যাটি আপনাকে জানিয়েছে যে আপনাকে পূর্ণসংখ্যার অ্যারে দেওয়া হবে। এখন আপনার সর্বাধিক পণ্যটি অর্জন করতে হবে যা আপনি এমন অর্জন করতে পারবেন যা আপনি একটি বর্ধমান অনুচ্ছেদের উপাদানগুলিকে গুন করেন। লক্ষ্য করার বিষয়টি হ'ল, আমাদের দীর্ঘতম বর্ধমান অনুচ্ছেদটি খুঁজে বের করার কথা নেই। আমাদের আরও ছোট উপসাগর থাকতে পারে তবে এটির সর্বোচ্চ পণ্য হওয়া উচিত।

উদাহরণ

একটি বর্ধমান অনুচ্ছেদের সর্বোচ্চ পণ্য

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

বর্ধমান উপগোষ্ঠীর সর্বাধিক পণ্য 10, 1000 Even যদিও দীর্ঘতম বর্ধমান অনুচ্ছেদটি {1, 2, 3, 4} হয়}

অভিগমন

সমস্যাটির সাদৃশ্য দীর্ঘতম বর্ধমান উপশক্তি সমস্যা। এই সমস্যাটির বিষয়ে সামান্য পরিবর্তন হ'ল দীর্ঘতম বর্ধমান অনুচ্ছেদটি অনুসন্ধান করার পরিবর্তে। আমাদের একটি বর্ধমান অনুচ্ছেদের সর্বাধিক পণ্য সন্ধান করতে হবে।

সুতরাং, এই সমস্যাটি সমাধান করার জন্য। সমস্যাটি সমাধান করার জন্য আমরা ব্রুট ফোর্স অ্যাপ্রোচ ব্যবহার করতে পারি। যদিও এই পদ্ধতিটি অদক্ষ তবে তা জানা উচিত। সুতরাং, ব্রুট ফোর্স পদ্ধতির মধ্যে, আমরা প্রথমে সমস্ত অনুচ্ছেদ তৈরি করব। উপসর্গগুলি উত্পাদন করার পরে, আমরা একটি পরীক্ষক ফাংশন তৈরি করি। চেকার ফাংশনে, আমরা সাবকিউনসটি বৈধ কিনা তা পরীক্ষা করে দেখি। চেকার ফাংশনের বৈধতাটির অর্থ হ'ল উপসর্গটি একটি ক্রমবর্ধমান অনুচ্ছেদ হওয়া উচিত। এর পরে, আমরা ক্রমবর্ধমান অনুচ্ছেদ থেকে পাওয়া সর্বাধিক পণ্য আপডেট করে চলেছি।

এখন প্রশ্ন হল আমরা কীভাবে সমস্যাটি সমাধান করব? সমস্যাটি দক্ষতার সাথে সমাধান করতে আমরা ডায়নামিক প্রোগ্রামিং ব্যবহার করি। সমস্যায় উত্তরণটি এলআইএস সমস্যার মতো that আমাদের ডিপি অ্যারে সর্বাধিক পণ্য সঞ্চয় করে যা আমরা যদি বর্তমান উপাদান পর্যন্ত সমস্ত উপাদান বিবেচনা করি তবে তা অর্জন করা যায়। এবং আরও একটি শর্ত রয়েছে যে অনুচ্ছেদে বর্তমান উপাদানটি থাকা উচিত। তারপরে ডিপি অ্যারের গণনা করার জন্য আমরা বর্তমান উপাদান থেকে শুরু করে উপাদানটির পিছনে দিকে নেস্টেড লুপটি চালাই। যদি আমরা বর্তমানের উপাদানটির চেয়ে ছোট একটি উপাদান খুঁজে পাই তবে আমরা আমাদের উত্তরটি আপডেট করব যদি ডিপি অ্যারেতে সূচকটিতে সেই উপাদানটিতে বর্তমান উপাদানটিকে গুণিত করা হয় তবে বর্তমানে সঞ্চিত মানের চেয়ে বেশি is

কোড

ক্রমবর্ধমান অনুগতির সর্বোচ্চ পণ্য সন্ধান করতে সি ++ কোড

#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) কারণ আমরা দুটি নেস্টেড লুপ ব্যবহার করছি। একটি যা সমস্ত উপাদানগুলির উপরে চলে এবং অন্য অভ্যন্তরীণ লুপটি বর্তমান উপাদান পর্যন্ত সমস্ত উপাদানগুলির উপরে চলে।

স্পেস জটিলতা ity

ও (এন) কারণ আমরা একটি একক মাত্রিক ডিপি টেবিল তৈরি করি। সুতরাং স্থান জটিলতা রৈখিক হয়।