నిర్దిష్ట వ్యత్యాసంతో జతల గరిష్ట మొత్తం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అకోలైట్ Coursera Delhivery ఫోర్కైట్స్ స్నాప్డీల్
అర్రే డైనమిక్ ప్రోగ్రామింగ్

“నిర్దిష్ట వ్యత్యాసంతో ఉన్న జతల గరిష్ట మొత్తం” సమస్య మీకు శ్రేణిని ఇచ్చిందని పేర్కొంది పూర్ణాంకాల మరియు ఒక పూర్ణాంకం K. అప్పుడు స్వతంత్ర జతల గరిష్ట మొత్తాన్ని కనుగొనమని అడుగుతారు. 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 శ్రేణి ఎందుకంటే మేము చిన్న ఉప సమస్యల ఫలితాన్ని నిల్వ చేస్తున్నాము. మేము దిగువ-అప్ 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), ఎందుకంటే మేము మొదట్లో శ్రేణిని క్రమబద్ధీకరించాము. మరియు విలీన విధమైన మరియు ఇతర సార్టింగ్ అల్గోరిథంలు O (NlogN) లో శ్రేణిని క్రమబద్ధీకరించగలవు. మాకు క్రమబద్ధీకరించిన ఇన్‌పుట్ అందించబడితే, మేము O (N) సమయంలో సమస్యను పరిష్కరించగలిగాము.

అంతరిక్ష సంక్లిష్టత

పై), శ్రేణిని క్రమబద్ధీకరించడానికి ఈ స్థలం అవసరం. మేము DP శ్రేణిని చేయకపోయినా మరియు DP పట్టిక కోసం అదే ఇన్పుట్ శ్రేణిని ఉపయోగించినప్పటికీ. ఆ పరిష్కారం ఇప్పటికీ అదే స్థల సంక్లిష్టతను కలిగి ఉంది ఎందుకంటే ఈ స్థలం క్రమబద్ధీకరించడానికి అవసరం.