Максимальна сума пар з конкретною різницею  


Рівень складності Легко
Часто запитують у Аколіт Coursera Делівері Фуркіти Snapdeal
масив Динамічне програмування

У задачі “Максимальна сума пар з конкретною різницею” зазначено, що вам дано масив цілих чисел і ціле число K. Тоді нам пропонують з’ясувати максимальну суму незалежних пар. Ми можемо створити пару двох цілих чисел, якщо вони мають абсолютну різницю меншу за K. Отже, нам потрібно знайти максимальну суму таких x пар, яка становить 2х чисел.

Приклад  

Максимальна сума пар з конкретною різницеюPin

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

Пояснення

Ми вибираємо 42, 43 і 5, 6. У нас були варіанти серед 4, 5 і 6. Отже, ми беремо максимальне значення серед них, роблячи результат = 96.

Підхід  

Завдання просить нас знайти максимальну суму, яку можна досягти, якщо ми з’єднаємо деякі елементи масив. Ми можемо поєднувати елементи за умови, що елементи повинні мати абсолютну різницю менше, ніж К. Перед тим, як вирішити проблему, ми сортувати масив. Таким чином ми обрізаємо наш пошуковий простір. Припустимо, у нас був несортований масив. Тоді нам довелося б пройти всі елементи для сполучення елементів. Але після сортування ми знаємо, що найбільшим елементом є саме той елемент, який передує йому. Тож ми перевіряємо, чи виконана умова.

Дивись також
Максимальна сума прямокутника у 2D-матриці

Якщо умова виконана, ми поєднуємо попередній і поточний елементи та додаємо результат задачі до останнього другого елемента (з поточного елемента). Але якщо умова не буде виконана. Ми залишаємо спарювання, і результат буде таким же, як і до попереднього елемента. Більш формально, result [i] = result [i-2] + input [i] + input [i-2], якщо сполучення виконується інакше result [i] = result [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

Код 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

Аналіз складності  

Складність часу 

O (NlogN), це тому, що ми спочатку сортували масив. А сортування злиття та інші алгоритми сортування можуть сортувати масив за O (NlogN). Якби нам надали відсортований вхід, ми могли б вирішити проблему за O (N) час.

Дивись також
Найбільша прямокутна підматриця, сума якої дорівнює 0

Складність простору

O (N), цей простір необхідний для сортування масиву. Навіть якби ми не створили масив DP і використовували б той самий вхідний масив для таблиці DP. Це рішення все ще має однакову складність простору, оскільки цей простір необхідний для сортування.