विशिष्ट फरक असलेल्या जोड्यांची जास्तीत जास्त बेरीज


अडचण पातळी सोपे
वारंवार विचारले एकत्रित Coursera दिल्लीवारी फोरकाइट्स Snapdeal
अरे डायनॅमिक प्रोग्रामिंग

“विशिष्ट फरक असलेल्या जोड्यांची जास्तीत जास्त बेरीज” ही समस्या सांगते की आपल्याला एक अ‍ॅरे दिली गेली आहे पूर्णांक आणि पूर्णांक के. त्यानंतर आम्हाला स्वतंत्र जोड्यांची जास्तीत जास्त बेरीज शोधण्यास सांगितले जाते. जर के बरोबर पूर्ण फरक असेल तर आम्ही दोन पूर्णांक जोडू शकतो. म्हणून, आम्हाला अशा x जोडांची जास्तीत जास्त बेरीज शोधणे आवश्यक आहे जे 2x संख्या आहेत.

उदाहरण

विशिष्ट फरक असलेल्या जोड्यांची जास्तीत जास्त बेरीज

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

स्पष्टीकरण

आम्ही ,२,, 42 आणि,, pick निवडतो. आमच्याकडे,,, आणि among होते. म्हणून, आम्ही त्यातील जास्तीत जास्त मूल्य घेतो = 43..

दृष्टीकोन

समस्या आम्हाला त्यातील काही घटक जोडल्यास प्राप्त होऊ शकणारी जास्तीत जास्त रक्कम शोधण्यास सांगते अॅरे. आम्ही घातलेल्या अट अंतर्गत घटकांची जोडणी करू शकतो की घटकांना के पेक्षा कमी फरक असणे आवश्यक आहे. समस्या सोडवण्यापूर्वी, आम्ही क्रमवारी अ‍ॅरे. अशाप्रकारे आम्ही आमच्या शोधातील जागा छाटत आहोत. आमच्याकडे अनसोर्टेड अ‍ॅरे होता याचा विचार करा नंतर घटक जोडण्यासाठी आम्हाला सर्व घटकांचा मागोवा घ्यावा लागेल. परंतु क्रमवारी लावल्यानंतर आपल्याला माहित आहे की सर्वात मोठा घटक हा त्यापूर्वीचा घटक आहे. तर अट पूर्ण झाल्याचे आम्ही तपासतो.

जर परिस्थिती समाधानी असेल तर आम्ही मागील आणि वर्तमान घटकाची जोडणी करतो आणि शेवटच्या दुसर्‍या घटकापर्यंत (वर्तमान घटकापासून) समस्येचा परिणाम जोडू. परंतु जर अट पूर्ण होत नसेल. आम्ही जोड्या सोडतो आणि परिणाम मागील घटकापर्यंत समान असतो. अधिक औपचारिकरित्या, परिणाम [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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी 

ओ (एनएलजीएन), कारण आपण सुरुवातीला अ‍ॅरेची क्रमवारी लावली होती. आणि मर्ज सॉर्ट आणि इतर सॉर्टिंग अल्गोरिदम ओ मध्ये ओरे (एनलॉगएन) मध्ये सॉर्ट करू शकतात. जर आम्हाला क्रमवारीकृत इनपुट प्रदान केले गेले असेल तर आम्ही ओ (एन) वेळेत समस्या सोडवू शकलो असतो.

स्पेस कॉम्प्लेक्सिटी

ओ (एन), अ‍ॅरेची क्रमवारी लावण्यासाठी ही जागा आवश्यक आहे. जरी आम्ही डीपी अ‍ॅरे केले नसते आणि डीपी टेबलसाठी समान इनपुट अ‍ॅरे वापरला असता. त्या सोल्यूशनमध्ये अद्यापही समान अवघडपणा आहे कारण ही जागा क्रमवारी लावण्यासाठी आवश्यक आहे.