Maximum sum of pairs with specific difference using dynamic programming
Dynamic programming is a powerful technique used to solve various optimization problems. In this article, we will explore how dynamic programming can be applied to find the maximum sum of pairs with a specific difference. We will provide an introduction to the problem, present the pseudocode algorithm with explanations, and analyze the time complexity of the solution. Finally, we will demonstrate the code implementation and provide an explanation of the output.
Introduction
The problem at hand is to find the maximum sum of pairs from a given array, such that the difference between the elements in each pair is equal to a specific value, k. We need to maximize the sum while ensuring that the difference constraint is satisfied.
Problem Statement
Given an array of integers, we need to find the maximum sum of pairs where the difference between the elements in each pair is less than or equal to a given value, k.
Pseudocode Algorithm
Let's understand the approach to solving this problem using dynamic programming:
1. Define a class called "Difference" to encapsulate the solution.
2. Create a method called "maxDifference" that takes an array of integers, the size of the array (n), and the difference constraint (k) as input.
3. If n is less than or equal to 1, return from the method.
4. Create two auxiliary arrays, "record" and "dp," of size n to store intermediate results.
5. Initialize the "record" array with the elements from the input array and set all values in the "dp" array to 0.
6. Sort the "record" array in ascending order.
7. Iterate through the "record" array starting from the second element:
a. Set dp[i] to dp[i-1].
b. If the difference between record[i] and record[i-1] is less than k:
- If i is greater than or equal to 2:
- Set dp[i] to the maximum value between dp[i] and dp[i-2] + record[i] + record[i-1].
- Otherwise, if i is 1:
- Set dp[i] to the maximum value between dp[i] and record[i] + record[i-1].
8. Print the array elements.
9. Print the calculated maximum sum, which is dp[n-1].
Explanation
Let's walk through an example to illustrate the working of the algorithm.
Given array: [1, 5, 7, 4, 15, 9, 21, 30] Difference (k): 3 After sorting the array: [1, 4, 5, 7, 9, 15, 21, 30] Pairs with a difference less than or equal to 3: - (5, 4) - (7, 9) The maximum sum of these pairs is: 5 + 4 + 7 + 9 = 25 Output: Array: 1 5 7 4 15 9 21 30 Result: 25
Code Solution
import java.util.Arrays;
/*
Java Program for
Maximum sum of pairs with specific difference using dynamic programming
*/
public class Difference
{
// Print array elements
public void printArray(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i]);
}
}
// Returns the maximum of given two numbers
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public void maxDifference(int[] arr, int n, int k)
{
if (n <= 1)
{
return;
}
// Auxiliary arrays
int record[] = new int[n];
int dp[] = new int[n];
// Assign array elements into record.
// And set dp initial value.
for (int i = 0; i < n; i++)
{
record[i] = arr[i];
dp[i] = 0;
}
// Sort record array
Arrays.sort(record);
for (int i = 1; i < n; ++i)
{
dp[i] = dp[i - 1];
if ((record[i] - record[i - 1]) < k)
{
if (i >= 2)
{
dp[i] = maxValue(dp[i], dp[i - 2] + record[i] + record[i - 1]);
}
else
{
dp[i] = maxValue(dp[i], record[i] + record[i - 1]);
}
}
}
// Print array elements
printArray(arr, n);
// Display calculated result
System.out.println("\n Result : " + dp[n - 1]);
}
public static void main(String[] args)
{
Difference task = new Difference();
// Array of integer elements
int arr[] = {
1 , 5 , 7 , 4 , 15 , 9 , 21 , 30
};
// Get number of element in array
int n = arr.length;
// Difference
int k = 3;
/*
(5 , 4) (7, 9)
5 + 4 + 7 + 9
--------------
25
*/
task.maxDifference(arr, n, k);
}
}Output
1 5 7 4 15 9 21 30
Result : 25// Include header file
#include <iostream>
#include <algorithm>
using namespace std;
/*
C++ Program for
Maximum sum of pairs with specific difference using dynamic programming
*/
class Difference
{
public:
// Print array elements
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
}
// Returns the maximum of given two numbers
int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
void maxDifference(int arr[], int n, int k)
{
if (n <= 1)
{
return;
}
// Auxiliary arrays
int record[n];
int dp[n];
// Assign array elements into record.
// And set dp initial value.
for (int i = 0; i < n; i++)
{
record[i] = arr[i];
dp[i] = 0;
}
// Sort record array
sort(record, record + n);
for (int i = 1; i < n; ++i)
{
dp[i] = dp[i - 1];
if ((record[i] - record[i - 1]) < k)
{
if (i >= 2)
{
dp[i] = this->maxValue(
dp[i], dp[i - 2] + record[i] + record[i - 1]);
}
else
{
dp[i] = this->maxValue(
dp[i], record[i] + record[i - 1]);
}
}
}
// Print array elements
this->printArray(arr, n);
// Display calculated result
cout << "\n Result : " << dp[n - 1] << endl;
}
};
int main()
{
Difference *task = new Difference();
// Array of integer elements
int arr[] = {
1 , 5 , 7 , 4 , 15 , 9 , 21 , 30
};
// Get number of element in array
int n = sizeof(arr) / sizeof(arr[0]);
// Difference
int k = 3;
/*
(5 , 4) (7, 9)
5 + 4 + 7 + 9
--------------
25
*/
task->maxDifference(arr, n, k);
return 0;
}Output
1 5 7 4 15 9 21 30
Result : 25// Include namespace system
using System;
/*
Csharp Program for
Maximum sum of pairs with specific difference using dynamic programming
*/
public class Difference
{
// Print array elements
public void printArray(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
}
// Returns the maximum of given two numbers
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public void maxDifference(int[] arr, int n, int k)
{
if (n <= 1)
{
return;
}
// Auxiliary arrays
int[] record = new int[n];
int[] dp = new int[n];
// Assign array elements into record.
// And set dp initial value.
for (int i = 0; i < n; i++)
{
record[i] = arr[i];
dp[i] = 0;
}
// Sort record array
Array.Sort(record);
for (int i = 1; i < n; ++i)
{
dp[i] = dp[i - 1];
if ((record[i] - record[i - 1]) < k)
{
if (i >= 2)
{
dp[i] = this.maxValue(
dp[i], dp[i - 2] + record[i] + record[i - 1]);
}
else
{
dp[i] = this.maxValue(
dp[i], record[i] + record[i - 1]);
}
}
}
// Print array elements
this.printArray(arr, n);
// Display calculated result
Console.WriteLine("\n Result : " + dp[n - 1]);
}
public static void Main(String[] args)
{
Difference task = new Difference();
// Array of integer elements
int[] arr = {
1 , 5 , 7 , 4 , 15 , 9 , 21 , 30
};
// Get number of element in array
int n = arr.Length;
// Difference
int k = 3;
/*
(5 , 4) (7, 9)
5 + 4 + 7 + 9
--------------
25
*/
task.maxDifference(arr, n, k);
}
}Output
1 5 7 4 15 9 21 30
Result : 25package main
import "sort"
import "fmt"
/*
Go Program for
Maximum sum of pairs with specific difference using dynamic programming
*/
// Print array elements
func printArray(arr[] int, n int) {
for i := 0 ; i < n ; i++ {
fmt.Print(" ", arr[i])
}
}
// Returns the maximum of given two numbers
func maxValue(a, b int) int {
if a > b {
return a
}
return b
}
func maxDifference(arr[] int, n int, k int) {
if n <= 1 {
return
}
// Auxiliary arrays
var record = make([] int, n)
var dp = make([] int, n)
// Assign array elements into record.
for i := 0 ; i < n ; i++ {
record[i] = arr[i]
}
// Sort record array
sort.Ints(record)
for i := 1 ; i < n ; i++ {
dp[i] = dp[i - 1]
if (record[i] - record[i - 1]) < k {
if i >= 2 {
dp[i] = maxValue(dp[i], dp[i - 2] + record[i] + record[i - 1])
} else {
dp[i] = maxValue(dp[i], record[i] + record[i - 1])
}
}
}
// Print array elements
printArray(arr, n)
// Display calculated result
fmt.Println("\n Result : ", dp[n - 1])
}
func main() {
// Array of integer elements
var arr = [] int {1, 5, 7, 4, 15, 9, 21, 30}
// Get number of element in array
var n int = len(arr)
// Difference
var k int = 3
/*
(5 , 4) (7, 9)
5 + 4 + 7 + 9
--------------
25
*/
maxDifference(arr, n, k)
}Output
1 5 7 4 15 9 21 30
Result : 25<?php
/*
Php Program for
Maximum sum of pairs with specific difference using dynamic programming
*/
class Difference
{
// Print array elements
public function printArray($arr, $n)
{
for ($i = 0; $i < $n; ++$i)
{
echo(" ".$arr[$i]);
}
}
// Returns the maximum of given two numbers
public function maxValue($a, $b)
{
if ($a > $b)
{
return $a;
}
return $b;
}
public function maxDifference($arr, $n, $k)
{
if ($n <= 1)
{
return;
}
$record = $arr;
// And set dp initial value.
$dp = array_fill(0, $n, 0);
// Sort record array
sort($record);
for ($i = 1; $i < $n; ++$i)
{
$dp[$i] = $dp[$i - 1];
if (($record[$i] - $record[$i - 1]) < $k)
{
if ($i >= 2)
{
$dp[$i] = $this->maxValue(
$dp[$i], $dp[$i - 2] + $record[$i] + $record[$i - 1]);
}
else
{
$dp[$i] = $this->maxValue(
$dp[$i], $record[$i] + $record[$i - 1]);
}
}
}
// Print array elements
$this->printArray($arr, $n);
// Display calculated result
echo("\n Result : ".$dp[$n - 1]."\n");
}
}
function main()
{
$task = new Difference();
// Array of integer elements
$arr = array(1, 5, 7, 4, 15, 9, 21, 30);
// Get number of element in array
$n = count($arr);
// Difference
$k = 3;
/*
(5 , 4) (7, 9)
5 + 4 + 7 + 9
--------------
25
*/
$task->maxDifference($arr, $n, $k);
}
main();Output
1 5 7 4 15 9 21 30
Result : 25/*
Node JS Program for
Maximum sum of pairs with specific difference using dynamic programming
*/
class Difference
{
// Print array elements
printArray(arr, n)
{
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + arr[i]);
}
}
// Returns the maximum of given two numbers
maxValue(a, b)
{
if (a > b)
{
return a;
}
return b;
}
maxDifference(arr, n, k)
{
if (n <= 1)
{
return;
}
// Auxiliary arrays
var record = Array(n).fill(0);
var dp = Array(n).fill(0);
// Assign array elements into record.
// And set dp initial value.
for (var i = 0; i < n; i++)
{
record[i] = arr[i];
dp[i] = 0;
}
// Sort record array
record.sort(function(a, b)
{
return a - b;
});
for (var i = 1; i < n; ++i)
{
dp[i] = dp[i - 1];
if ((record[i] - record[i - 1]) < k)
{
if (i >= 2)
{
dp[i] = this.maxValue(
dp[i], dp[i - 2] + record[i] + record[i - 1]);
}
else
{
dp[i] = this.maxValue(
dp[i], record[i] + record[i - 1]);
}
}
}
// Print array elements
this.printArray(arr, n);
// Display calculated result
console.log("\n Result : " + dp[n - 1]);
}
}
function main()
{
var task = new Difference();
// Array of integer elements
var arr = [1, 5, 7, 4, 15, 9, 21, 30];
// Get number of element in array
var n = arr.length;
// Difference
var k = 3;
/*
(5 , 4) (7, 9)
5 + 4 + 7 + 9
--------------
25
*/
task.maxDifference(arr, n, k);
}
main();Output
1 5 7 4 15 9 21 30
Result : 25# Python 3 Program for
# Maximum sum of pairs with specific difference using dynamic programming
class Difference :
# Print list elements
def printArray(self, arr, n) :
i = 0
while (i < n) :
print(" ", arr[i], end = "")
i += 1
# Returns the maximum of given two numbers
def maxValue(self, a, b) :
if (a > b) :
return a
return b
def maxDifference(self, arr, n, k) :
if (n <= 1) :
return
# Auxiliary lists
record = arr.copy()
record.sort()
dp = [0] * (n)
i = 1
while (i < n) :
dp[i] = dp[i - 1]
if ((record[i] - record[i - 1]) < k) :
if (i >= 2) :
dp[i] = self.maxValue(dp[i],
dp[i - 2] + record[i] + record[i - 1])
else :
dp[i] = self.maxValue(dp[i],
record[i] + record[i - 1])
i += 1
# Print list elements
self.printArray(arr, n)
# Display calculated result
print("\n Result : ", dp[n - 1])
def main() :
task = Difference()
# Array of integer elements
arr = [1, 5, 7, 4, 15, 9, 21, 30]
# Get number of element in list
n = len(arr)
# Difference
k = 3
# (5 , 4) (7, 9)
# 5 + 4 + 7 + 9
# --------------
# 25
task.maxDifference(arr, n, k)
if __name__ == "__main__": main()Output
1 5 7 4 15 9 21 30
Result : 25# Ruby Program for
# Maximum sum of pairs with specific difference using dynamic programming
class Difference
# Print array elements
def printArray(arr, n)
i = 0
while (i < n)
print(" ", arr[i])
i += 1
end
end
# Returns the maximum of given two numbers
def maxValue(a, b)
if (a > b)
return a
end
return b
end
def maxDifference(arr, n, k)
if (n <= 1)
return
end
# Auxiliary arrays
record = arr.sort
dp = Array.new(n) {0}
# Sort record array
record.sort
i = 1
while (i < n)
dp[i] = dp[i - 1]
if ((record[i] - record[i - 1]) < k)
if (i >= 2)
dp[i] = self.maxValue(
dp[i], dp[i - 2] + record[i] + record[i - 1])
else
dp[i] = self.maxValue(
dp[i], record[i] + record[i - 1])
end
end
i += 1
end
# Print array elements
self.printArray(arr, n)
# Display calculated result
print("\n Result : ", dp[n - 1], "\n")
end
end
def main()
task = Difference.new()
# Array of integer elements
arr = [1, 5, 7, 4, 15, 9, 21, 30]
# Get number of element in array
n = arr.length
# Difference
k = 3
# (5 , 4) (7, 9)
# 5 + 4 + 7 + 9
# --------------
# 25
task.maxDifference(arr, n, k)
end
main()Output
1 5 7 4 15 9 21 30
Result : 25
/*
Scala Program for
Maximum sum of pairs with specific difference using dynamic programming
*/
class Difference()
{
// Print array elements
def printArray(arr: Array[Int], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print(" " + arr(i));
i += 1;
}
}
// Returns the maximum of given two numbers
def maxValue(a: Int, b: Int): Int = {
if (a > b)
{
return a;
}
return b;
}
def maxDifference(arr: Array[Int], n: Int, k: Int): Unit = {
if (n <= 1)
{
return;
}
// Auxiliary arrays
var record: Array[Int] = arr.sorted;
var dp: Array[Int] = Array.fill[Int](n)(0);
var i: Int = 1;
while (i < n)
{
dp(i) = dp(i - 1);
if ((record(i) - record(i - 1)) < k)
{
if (i >= 2)
{
dp(i) = maxValue(
dp(i), dp(i - 2) + record(i) + record(i - 1));
}
else
{
dp(i) = maxValue(
dp(i), record(i) + record(i - 1));
}
}
i += 1;
}
// Print array elements
printArray(arr, n);
// Display calculated result
println("\n Result : " + dp(n - 1));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Difference = new Difference();
// Array of integer elements
var arr: Array[Int] = Array(1, 5, 7, 4, 15, 9, 21, 30);
// Get number of element in array
var n: Int = arr.length;
// Difference
var k: Int = 3;
/*
(5 , 4) (7, 9)
5 + 4 + 7 + 9
--------------
25
*/
task.maxDifference(arr, n, k);
}
}Output
1 5 7 4 15 9 21 30
Result : 25import Foundation;
/*
Swift 4 Program for
Maximum sum of pairs with specific difference using dynamic programming
*/
class Difference
{
// Print array elements
func printArray(_ arr: [Int], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
}
// Returns the maximum of given two numbers
func maxValue(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
return a;
}
return b;
}
func maxDifference(_ arr: [Int], _ n: Int, _ k: Int)
{
if (n <= 1)
{
return;
}
// Auxiliary arrays
var record: [Int] = Array(repeating: 0, count: n);
var dp: [Int] = Array(repeating: 0, count: n);
var i: Int = 0;
// Assign array elements into record.
while (i < n)
{
record[i] = arr[i];
i += 1;
}
// Sort record array
record = record.sorted();
i = 1;
while (i < n)
{
dp[i] = dp[i - 1];
if ((record[i] - record[i - 1]) < k)
{
if (i >= 2)
{
dp[i] = self.maxValue(
dp[i], dp[i - 2] + record[i] + record[i - 1]);
}
else
{
dp[i] = self.maxValue(
dp[i], record[i] + record[i - 1]);
}
}
i += 1;
}
// Print array elements
self.printArray(arr, n);
// Display calculated result
print("\n Result : ", dp[n - 1]);
}
}
func main()
{
let task: Difference = Difference();
// Array of integer elements
let arr: [Int] = [1, 5, 7, 4, 15, 9, 21, 30];
// Get number of element in array
let n: Int = arr.count;
// Difference
let k: Int = 3;
/*
(5 , 4) (7, 9)
5 + 4 + 7 + 9
--------------
25
*/
task.maxDifference(arr, n, k);
}
main();Output
1 5 7 4 15 9 21 30
Result : 25/*
Kotlin Program for
Maximum sum of pairs with specific difference using dynamic programming
*/
class Difference
{
// Print array elements
fun printArray(arr: Array < Int > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print(" " + arr[i]);
i += 1;
}
}
// Returns the maximum of given two numbers
fun maxValue(a: Int, b: Int): Int
{
if (a > b)
{
return a;
}
return b;
}
fun maxDifference(arr: Array < Int > , n: Int, k: Int): Unit
{
if (n <= 1)
{
return;
}
// Auxiliary arrays
var record: Array < Int > = Array(n)
{
0
};
var dp: Array < Int > = Array(n)
{
0
};
var i = 0;
// Assign array elements into record.
// And set dp initial value.
while (i < n)
{
record[i] = arr[i];
dp[i] = 0;
i += 1;
}
// Sort record array
record.sort();
i = 1;
while (i < n)
{
dp[i] = dp[i - 1];
if ((record[i] - record[i - 1]) < k)
{
if (i >= 2)
{
dp[i] = this.maxValue(
dp[i], dp[i - 2] + record[i] + record[i - 1]);
}
else
{
dp[i] = this.maxValue(
dp[i], record[i] + record[i - 1]);
}
}
i += 1;
}
// Print array elements
this.printArray(arr, n);
// Display calculated result
println("\n Result : " + dp[n - 1]);
}
}
fun main(args: Array < String > ): Unit
{
val task: Difference = Difference();
// Array of integer elements
val arr: Array < Int > = arrayOf(1, 5, 7, 4, 15, 9, 21, 30);
// Get number of element in array
val n: Int = arr.count();
// Difference
val k: Int = 3;
/*
(5 , 4) (7, 9)
5 + 4 + 7 + 9
--------------
25
*/
task.maxDifference(arr, n, k);
}Output
1 5 7 4 15 9 21 30
Result : 25Time Complexity
The time complexity of this solution is dominated by the sorting step, which has a time complexity of O(n log n). The subsequent loop takes linear time, i.e., O(n). Therefore, the overall time complexity of the algorithm is O(n log n).
Now that we have explored the problem statement, algorithm, and code implementation, you should have a good understanding of solving the maximum sum of pairs problem with a specific difference using dynamic programming. By applying the pseudocode algorithm, you can find the maximum sum efficiently while adhering to the given difference constraint.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment