Հատուկ տարբերությամբ զույգերի առավելագույն գումար


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Ակոլիտ Coursera Առաքում Ֆուրկիտներ Snapdeal
Դասավորություն Դինամիկ ծրագրավորում

«Հատուկ տարբերությամբ զույգերի առավելագույն գումար» խնդիրը նշում է, որ ձեզ տրվում է զանգված ամբողջական թվերը և ամբողջ թիվ 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 զանգված, քանի որ մենք պահպանում ենք ավելի փոքր ենթախնդիրների արդյունքը: Մենք համատեղում ենք այս փոքր ենթածրագրերի արդյունքը `գտնելու բուն խնդրի արդյունքը, ինչպես անում ենք ներքևից վերև գտնվող Հ-ում:

Կոդ

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

Java կոդ `հատուկ տարբերությամբ զույգերի առավելագույն գումարը գտնելու համար

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

Բարդության վերլուծություն

Timeամանակի բարդություն 

O (NlogN), սա այն պատճառով, որ մենք ի սկզբանե դասավորել էինք զանգվածը: Եվ միաձուլման տեսակավորման և այլ տեսակավորման ալգորիթմները կարող են զանգվածը տեսակավորել O- ում (NlogN): Եթե ​​մեզ տրամադրվեր տեսակավորված մուտք, մենք կարող էինք խնդիրը լուծել O (N) ժամանակում:

Տիեզերական բարդություն

ՎՐԱ), այս տարածքը պահանջվում է զանգվածը տեսակավորելու համար: Նույնիսկ եթե մենք չէինք կազմել DP զանգվածը և օգտագործեինք նույն մուտքային զանգվածը DP աղյուսակի համար: Այդ լուծումը դեռ ունի տիեզերական նույն բարդությունը, քանի որ տեսակավորելու համար այս տարածքը պահանջվում է: