Skip to main content

Maximum sum of pairs with specific difference using dynamic programming

Here given code implementation process.

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
Last updated on by Kalkicode




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