Skip to main content

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 : 25
package 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 : 25
import 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 : 25

Time 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.





Comment

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