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