அதிகரித்து வரும் அடுத்தடுத்த அதிகபட்ச தயாரிப்பு


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அகோலைட் GE ஹெல்த்கேர் ஹேக்கர் தரவரிசை ஐபிஎம் SnapChat யாகூ
அணி டைனமிக் புரோகிராமிங்

சிக்கல் அறிக்கை

“அதிகரித்து வரும் அடுத்தடுத்த அதிகபட்ச தயாரிப்பு” என்ற சிக்கல் உங்களுக்கு முழு எண்களை வழங்குவதாகக் கூறுகிறது. இப்போது நீங்கள் அடையக்கூடிய அதிகபட்ச உற்பத்தியைக் கண்டுபிடிக்க வேண்டும், இது அதிகரிக்கும் அடுத்தடுத்த கூறுகளை நீங்கள் பெருக்குகிறது. கவனிக்க வேண்டிய விஷயம் என்னவென்றால், மிக நீண்ட காலமாக அதிகரித்து வருவதை நாம் கண்டுபிடிக்க வேண்டியதில்லை. எங்களிடம் ஒரு சிறிய தொடர்ச்சி இருக்கலாம், ஆனால் அதற்கு அதிகபட்ச தயாரிப்பு இருக்க வேண்டும்.

உதாரணமாக

அதிகரித்து வரும் அடுத்தடுத்த அதிகபட்ச தயாரிப்பு

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

அதிகரித்து வரும் அடுத்தடுத்த அதிகபட்ச தயாரிப்பு 10, 1000 ஆகும். மிக நீண்ட காலமாக அதிகரித்து வருவது {1, 2, 3, 4 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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

O (N ^ 2) ஏனெனில் நாங்கள் இரண்டு உள்ளமை சுழல்களைப் பயன்படுத்துகிறோம். ஒன்று அனைத்து உறுப்புகளுக்கும் மேலாக இயங்குகிறது, மற்றொன்று உள் வளையமானது தற்போதைய உறுப்பு வரை அனைத்து உறுப்புகளுக்கும் மேல் இயங்கும்.

விண்வெளி சிக்கலானது

ஓ (என்) ஏனெனில் நாங்கள் ஒரு பரிமாண டிபி அட்டவணையை உருவாக்குகிறோம். இதனால் விண்வெளி சிக்கலானது நேரியல் ஆகும்.