विशिष्ट भिन्नताका साथ जोडीहरूको अधिकतम योग


कठिनाई तह सजिलो
बारम्बार सोधिन्छ समग्र Coursera दिल्लीवरी फोरकाइट्स स्नैपडल
एरे डायनामिक प्रोग्रामिंग

समस्या "विशेष भिन्नताका साथ जोडीहरूको अधिकतम योग" बताउँछ कि तपाईंलाई एर्रे दिइयो पूर्णांकहरू र एक पूर्णांक K. त्यसोभए हामीलाई स्वतन्त्र जोडाहरूको अधिकतम योगफल फेला पार्न सोधिन्छ। हामी दुई पूर्णांक जोडी गर्न सक्दछौं यदि तिनीहरूसँग K भन्दा कमको पूर्ण भिन्नता छ। त्यसैले, हामी यस्तो x जोडी को अधिकतम योग 2x संख्या को खोज्न आवश्यक छ।

उदाहरणका

विशिष्ट भिन्नताका साथ जोडीहरूको अधिकतम योग

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

स्पष्टीकरण

हामी pick२,, 42, र,, pick छान्छौं। हामीसँग,,,, र 43. मा विकल्पहरू थिए। त्यसो भए, हामी परिणाम among। Making बनाउँदै तिनीहरूमा अधिकतम मूल्य लिन्छौं।

दृष्टिकोण

समस्याले हामीलाई अधिकतम योगफल फेला पार्न सोध्छ यदि हामी यसका केही तत्वहरू जोड्छौं भने प्राप्त गर्न सकिन्छ array। हामी लागू गरिएको सर्त अन्तर्गत एलिमेन्टिहरु जोडी गर्न सक्छौं कि एलिमेन्ट्स का K भन्दा कमको पूर्ण भिन्नता हुनु पर्छ। समस्या समाधान गर्नु अघि हामी भाग्य एर्रे। यस तरीकाले हामी हाम्रो खोजी ठाउँ छाँटिरहेका छौं। विचार गर्नुहोस् हामीसंग एक अनसोर्टेड एर्रे थियो। त्यसो भए हामीले एलिमेन्ट पेयरिंगका लागि सबै एलिमेन्टहरूलाई ट्र्यावर्स गर्नुपर्नेछ। तर क्रमबद्ध गरिसके पछि हामीलाई थाहा छ कि सब भन्दा ठूलो एलिमेन्ट मात्र एलिमेन्ट हुन्छ जुन यसमा अघिल्लो हुन्छ। त्यसैले हामी जाँच गर्छौं यदि कन्डिसन सन्तुष्ट छ कि छैन।

यदि सर्त सन्तुष्ट छ भने, हामी अघिल्लो र वर्तमान तत्व जोडी गर्छौं र अन्तिम दोस्रो एलिमेन्ट (हालको एलिमेन्टबाट) सम्म समस्याका लागि परिणाम थप्छौं। तर यदि अवस्था सन्तुष्ट छैन। हामी पेयरि leave छाड्छौं र परिणाम अघिल्लो एलिमेन्ट नभएसम्म उस्तै हुन्छ। अधिक औपचारिक रूपमा, परिणाम [i] = परिणाम [i-2] + इनपुट [i] + इनपुट [i-2], यदि पेयरि else्ग गरियो भने परिणाम हुन्छ [i] = परिणाम [i-1]। यहाँ यो परिणाम एरे हाम्रो हो DP एरे किनभने हामी साना सबप्रोब्लम्सको नतिजा भण्डार गर्दैछौं। हामी यी सानो सबप्रोब्लम्सको परिणामलाई संयोजन गर्दछौं मूल समस्याको परिणाम फेला पार्नको लागि हामी तल-अप डीपीमा गर्‍यौं।

कोड

C ++ कोड विशिष्ट भिन्नताका साथ जोडीहरूको अधिकतम योग फेला पार्न

#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

जटिलता विश्लेषण

समय जटिलता 

O (NlogN), यो किनभने हामीले सुरुमा एरे सॉर्ट गरेका थियौं। र मर्ज क्रमबद्ध र अन्य क्रमबद्ध एल्गोरिथ्महरू O (NlogN) मा एरे क्रमबद्ध गर्न सक्दछ। यदि हामीलाई क्रमबद्ध गरिएको इनपुट प्रदान गरिएको थियो भने हामी O (N) समयमा समस्या समाधान गर्न सक्दछौं।

ठाउँ जटिलता

O (N), यो ठाउँ एर्रे क्रमबद्ध गर्नका लागि आवश्यक छ। यदि हामीले DP एर्रे बनाएका छैनौं र DP तालिकाको लागि समान इनपुट एर्रे प्रयोग गरेका छौं। त्यो समाधानसँग अझै उस्तै ठाउँ जटिलता छ किनकि यो ठाउँ क्रमबद्ध गर्नका लागि आवश्यक छ।