Максимална сума на парови со специфична разлика


Ниво на тешкотија Лесно
Често прашувано во Аколит 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

Анализа на сложеност

Временска комплексност 

О (NlogN), тоа е затоа што првично ја сортиравме низата. И спојување на сортирање и други алгоритми за сортирање може да ја сортираат низата во O (NlogN). Ако ни беше обезбеден сортиран влез, ќе можевме да го решиме проблемот во O (N) време.

Комплексноста на просторот

НА), овој простор е потребен за сортирање на низата. Дури и да не ја направевме низата ДП и ќе ја користевме истата влезна низа за табелата со ДП. Тоа решение сè уште ја има истата сложеност во просторот затоа што овој простор е потребен за сортирање.