ከተለየ ልዩነት ጋር ከፍተኛው ጥንድ ድምር  


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የተከማቸ Coursera አቅርቦት አራት ኪይትስ Snapdeal
ሰልፍ ተለዋዋጭ ፕሮግራም

ችግሩ “ከተለየ ልዩነት ጋር ከፍተኛው ጥንድ ድምር” አንድ ድርድር ይሰጥዎታል ይላል ኢንቲጀሮች እና አንድ ኢንቲጀር ኬ ከዚያ ከፍተኛውን የነፃ ጥንድ ድምር እንድናገኝ እንጠየቃለን ፡፡ ከቁጥር በታች የሆነ ፍጹም ልዩነት ካላቸው ሁለት ኢቲጀሮችን ማጣመር እንችላለን ፣ ስለሆነም 2x ቁጥሮች የሆኑ እንደዚህ ያሉ x ጥንዶች ከፍተኛውን ድምር መፈለግ ይጠበቅብናል ፡፡

ለምሳሌ  

ከተለየ ልዩነት ጋር ከፍተኛው ጥንድ ድምርጭንቅላታም መያያዣ መርፌ

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

ማስረጃ

እኛ እንመርጣለን 42 ፣ 43 እና 5 ፣ 6. ከ 4 ፣ 5 እና 6 መካከል አማራጮች ነበሩን ስለሆነም ውጤቱን በማምጣት መካከል ከፍተኛውን እሴት እንወስዳለን = 96 ፡፡

ቀረበ  

አንዳንድ ነገሮችን ከጣምረን ሊደረስበት የሚችል ከፍተኛውን ድምር እንድናገኝ ችግሩ ይጠይቀናል ደርድር. ንጥረ ነገሮቹን ከመፍትሔው በፊት ከ K. ያነሱ ፍጹም ፍጹም ልዩነት እንዲኖራቸው በተጫነው ሁኔታ አባሎችን ማጣመር እንችላለን ዓይነት ድርድሩ። በዚህ መንገድ የፍለጋ ቦታችንን እየቆረጥን ነው ፡፡ ያልተለየ ድርድር እንደነበረን ያስቡ ፡፡ ከዚያ አንድን ንጥረ ነገር ለማጣመር ሁሉንም አካላት ማለፍ አለብን። ግን ከተለየን በኋላ ትልቁ ንጥረ ነገር ከዚህ በፊት ያለው ንጥረ ነገር ብቻ መሆኑን እናውቃለን ፡፡ ስለዚህ ሁኔታው ​​ከተሟላ እንፈትሻለን ፡፡

ተመልከት
በ 2 ዲ ማትሪክስ ውስጥ ከፍተኛው ድምር አራት ማዕዘን

ሁኔታው ከተሟላ የቀደመውን እና የአሁኑን ንጥረ ነገር እናጣምረው እና እስከ ሁለተኛው ሁለተኛ አካል ድረስ (አሁን ካለው ንጥረ ነገር) ድረስ ለችግሩ ውጤቱን እንጨምራለን ፡፡ ግን ሁኔታው ​​ካልተሟላ ፡፡ ተጣማጅውን እንተወዋለን ውጤቱም እስከ ቀዳሚው ንጥረ ነገር ድረስ ካለው ጋር ተመሳሳይ ነው ፡፡ በመደበኛነት ፣ ውጤት [i] = ውጤት [i-2] + ግብዓት [i] + ግብዓት [i-2] ፣ ማጣመር ከተከናወነ ሌላ ውጤት [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

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት 

ኦ (NlogN) ፣ ይህ የሆነው እኛ መጀመሪያ ድርድርን ስለደረደርነው ነው ፡፡ እና አንድ ዓይነት እና ሌሎች የማጣቀሻ ስልተ ቀመሮችን በ O (NlogN) ውስጥ መደርደር ይችላሉ ፡፡ የተስተካከለ ግብዓት ቢሰጠን ኖሮ በ O (N) ጊዜ ውስጥ ችግሩን መፍታት እንችል ነበር ፡፡

ተመልከት
ድምር 0 የሆነ ትልቁ አራት ማዕዘን ንዑስ ማትሪክስ

የቦታ ውስብስብነት

ኦ (ኤን) ፣ ድርድርን ለመደርደር ይህ ቦታ ያስፈልጋል። ምንም እንኳን የዲፒ ድርድር ባናደርግ እና ለዲፒ ሰንጠረዥ ተመሳሳይ የግብዓት ድርድርን ብጠቀም እንኳን ፡፡ ይህ መፍትሄ አሁንም ተመሳሳይ የቦታ ውስብስብነት አለው ምክንያቱም ይህ ቦታ ለመደርደር ያስፈልጋል ፡፡