विशिष्ट अंतर के साथ जोड़े की अधिकतम राशि


कठिनाई स्तर आसान
में अक्सर पूछा एकोलाइट Coursera Delhivery चौपाई स्नैपडील
ऐरे गतिशील प्रोग्रामिंग

समस्या "विशिष्ट अंतर के साथ जोड़े की अधिकतम राशि" बताती है कि आपको एक सरणी दी गई है पूर्णांकों और एक पूर्णांक K. तब हमें स्वतंत्र जोड़े की अधिकतम राशि ज्ञात करने के लिए कहा जाता है। हम दो पूर्णांकों को जोड़ सकते हैं यदि उनके पास K से कम का पूर्ण अंतर है, तो, हमें ऐसे एक्स जोड़े की अधिकतम राशि ज्ञात करनी होगी जो 2x संख्या है।

उदाहरण

विशिष्ट अंतर के साथ जोड़े की अधिकतम राशि

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

व्याख्या

हम 42, 43 और 5 को चुनते हैं, 6. हमारे पास 4, 5 और 6 के बीच विकल्प थे। इसलिए, हम परिणाम के लिए अधिकतम मूल्य लेते हैं = 96।

दृष्टिकोण

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

यदि स्थिति संतुष्ट है, तो हम पिछले और वर्तमान तत्व को जोड़ते हैं और अंतिम दूसरे तत्व (वर्तमान तत्व से) तक समस्या के लिए परिणाम जोड़ते हैं। लेकिन अगर हालत संतुष्ट नहीं है। हम बाँधना छोड़ देते हैं और परिणाम पिछले तत्व के समान है। औपचारिक रूप से, परिणाम [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

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

समय जटिलता 

O (NlogN), इसका कारण यह है कि हमने शुरुआत में सरणी को क्रमबद्ध किया था। और सॉर्ट और अन्य सॉर्टिंग एल्गोरिदम ओ (NlogN) में सरणी को सॉर्ट कर सकते हैं। यदि हमें एक हल किए गए इनपुट के साथ प्रदान किया गया था, तो हम ओ (एन) समय में समस्या को हल कर सकते थे।

अंतरिक्ष जटिलता

पर), यह स्थान सरणी को छांटने के लिए आवश्यक है। यहां तक ​​कि अगर हमने डीपी सरणी नहीं बनाई है और डीपी टेबल के लिए उसी इनपुट सरणी का उपयोग किया होगा। उस समाधान में अभी भी एक ही स्थान की जटिलता है क्योंकि यह स्थान छंटाई के लिए आवश्यक है।