குறிப்பிட்ட வேறுபாடு கொண்ட ஜோடிகளின் அதிகபட்ச தொகை


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அகோலைட் Coursera கூடுதலாக Delhivery ஃபோர்கைட்டுகள் Snapdeal
அணி டைனமிக் புரோகிராமிங்

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

உதாரணமாக

குறிப்பிட்ட வேறுபாடு கொண்ட ஜோடிகளின் அதிகபட்ச தொகை

42, 43, 4, 5, 6, 12
96

விளக்கம்

நாங்கள் 42, 43, மற்றும் 5, 6 ஐத் தேர்வு செய்கிறோம். 4, 5 மற்றும் 6 இல் எங்களுக்கு விருப்பங்கள் இருந்தன. ஆகவே, அவற்றில் அதிகபட்ச மதிப்பை நாம் எடுத்துக்கொள்கிறோம் = 96.

அணுகுமுறை

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

நிபந்தனை திருப்தி அடைந்தால், முந்தைய மற்றும் தற்போதைய உறுப்பை இணைத்து, கடைசி இரண்டாவது உறுப்பு வரை (தற்போதைய உறுப்பிலிருந்து) சிக்கலுக்கான முடிவைச் சேர்ப்போம். ஆனால் நிபந்தனை திருப்தி அடையவில்லை என்றால். நாங்கள் இணைப்பதை விட்டுவிடுகிறோம், இதன் விளைவாக முந்தைய உறுப்பு வரை இருக்கும். இன்னும் முறையாக, முடிவு [i] = முடிவு [i-2] + உள்ளீடு [i] + உள்ளீடு [i-2], இணைத்தல் வேறு செய்யப்பட்டால் [i] = முடிவு [i-1]. இங்கே இந்த முடிவு வரிசை நம்முடையது DP வரிசை ஏனெனில் சிறிய துணை சிக்கல்களின் முடிவை நாங்கள் சேமித்து வருகிறோம். கீழேயுள்ள டி.பியில் நாம் செய்வது போல அசல் சிக்கலின் முடிவைக் கண்டறிய இந்த சிறிய துணைப் பிரச்சினைகளின் முடிவை இணைக்கிறோம்.

குறியீடு

குறிப்பிட்ட வித்தியாசத்துடன் அதிகபட்ச ஜோடிகளைக் கண்டுபிடிக்க சி ++ குறியீடு

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int input[] = {42, 43, 4, 5, 6, 12};
    int n = sizeof(input)/sizeof(int);
    int K = 4;
    sort(input, input+n);
    int dp[n];
    memset(dp, 0, sizeof dp);
    for(int i=1;i<n;i++){
        dp[i] = dp[i-1];
        if(input[i]-input[i-1] < K)
            dp[i] = max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
    }
    cout<<dp[n-1];
    return 0;
}
96

குறிப்பிட்ட வித்தியாசத்துடன் அதிகபட்ச ஜோடிகளைக் கண்டுபிடிக்க ஜாவா குறியீடு

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int input[] = {42, 43, 4, 5, 6, 12};
      int n = input.length;
      int K = 4;
      Arrays.sort(input);
      int dp[] = new int[n];
      dp[0] = 0;
      for(int i=1;i<n;i++){
          dp[i] = dp[i-1];
          if(input[i]-input[i-1] < K)
              dp[i] = Math.max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
      }
    System.out.println(dp[n-1]);
  }
}
96

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

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

ஓ (NlogN), ஏனென்றால் நாங்கள் ஆரம்பத்தில் வரிசையை வரிசைப்படுத்தியிருந்தோம். மற்றும் வரிசைப்படுத்தல் மற்றும் பிற வரிசையாக்க வழிமுறைகள் O (NlogN) இல் வரிசையை வரிசைப்படுத்தலாம். வரிசைப்படுத்தப்பட்ட உள்ளீடு எங்களுக்கு வழங்கப்பட்டிருந்தால், O (N) நேரத்தில் சிக்கலை தீர்க்க முடியும்.

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

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