Find maximum sum bitonic sub sequence using dynamic programming
Here given code implementation process.
// C Program
// Find maximum sum bitonic sub sequence using dynamic programming
#include <stdio.h>
#include <limits.h>
// Function which is display array elements
void display(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
printf("%d ", arr[i]);
}
}
// Returns a max value of two integers
int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
void maxSumBitonicSequence(int arr[], int n)
{
// This is collects the sum of bitonic subsequence from left to right.
int sumLeftToRight[n];
// This is collects the sum of bitonic subsequence from right to left.
int sumRightToLeft[n];
// Initial value of result is minimum value.
int result = INT_MIN;
// Set initial value of sum
for (int i = 0; i < n; ++i)
{
sumLeftToRight[i] = arr[i];
sumRightToLeft[i] = arr[i];
}
// Calculate right to left maximum bitonic sum.
// This loop start with second last element and
// Execute until the its value is not -1.
for (int i = n - 2; i >= 0; --i)
{
// This loop start with last element and execute
// until the its value is greater than [i].
for (int j = n - 1; j > i; --j)
{
if (arr[i] > arr[j] &&
(sumRightToLeft[i] < sumRightToLeft[j] + arr[i]))
{
// Update sum value
sumRightToLeft[i] = sumRightToLeft[j] + arr[i];
}
}
}
// Calculate left to right maximum bitonic sum
for (int i = 1; i < n; ++i)
{
for (int j = 0; j < i; ++j)
{
if (arr[i] > arr[j] &&
(sumLeftToRight[i] < sumLeftToRight[j] + arr[i]))
{
// Update sum value
sumLeftToRight[i] = sumLeftToRight[j] + arr[i];
}
}
}
// Calculate maximum bitonic sum using left and right sum.
for (int i = 0; i < n; ++i)
{
result = maxValue(result ,
(sumRightToLeft[i] + sumLeftToRight[i] - arr[i]));
}
printf("\n Given sequence : ");
display(arr, n);
printf("\n Result : %d", result);
}
int main()
{
// Array of integer elements
int arr1[] = {
4 , 1 , 3 , 9 , 3 , -2 , 2 , 8 , 3 , 1 , 1 , 4 , 5
};
int arr2[] = {
45 , 2 , 1 , 14 , 15 , 18 , 20 , 1 , -12 , 2 , 4
};
// Test A
int n = sizeof(arr1) / sizeof(arr1[0]);
// [1 + 3 + 9 + 8 + 5]
// maximum sum bitonic subsequence
// 26
maxSumBitonicSequence(arr1, n);
// Test B
n = sizeof(arr2) / sizeof(arr2[0]);
// [2 + 14 + 15 + 18 + 20 + 4]
// maximum sum bitonic subsequence
// 73
maxSumBitonicSequence(arr2, n);
return 0;
}
Output
Given sequence : 4 1 3 9 3 -2 2 8 3 1 1 4 5
Result : 26
Given sequence : 45 2 1 14 15 18 20 1 -12 2 4
Result : 73
/*
Java Program for
Find maximum sum bitonic sub sequence using dynamic programming
*/
public class BitonicSequence
{
// Function which is display array elements
public void display(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i] );
}
}
// Returns a max value of two integers
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public void maxSumBitonicSequence(int[] arr, int n)
{
// This is collects the sum of bitonic subsequence from left to right.
int[] sumLeftToRight = new int[n];
// This is collects the sum of bitonic subsequence from right to left.
int[] sumRightToLeft = new int[n];
// Initial value of result is minimum value.
int result = Integer.MIN_VALUE;
// Set initial value of sum
for (int i = 0; i < n; ++i)
{
sumLeftToRight[i] = arr[i];
sumRightToLeft[i] = arr[i];
}
// Calculate right to left maximum bitonic sum.
// This loop start with second last element and
// Execute until the its value is not -1.
for (int i = n - 2; i >= 0; --i)
{
// This loop start with last element and execute
// until the its value is greater than [i].
for (int j = n - 1; j > i; --j)
{
if (arr[i] > arr[j] &&
(sumRightToLeft[i] < sumRightToLeft[j] + arr[i]))
{
// Update sum value
sumRightToLeft[i] = sumRightToLeft[j] + arr[i];
}
}
}
// Calculate left to right maximum bitonic sum
for (int i = 1; i < n; ++i)
{
for (int j = 0; j < i; ++j)
{
if (arr[i] > arr[j] &&
(sumLeftToRight[i] < sumLeftToRight[j] + arr[i]))
{
// Update sum value
sumLeftToRight[i] = sumLeftToRight[j] + arr[i];
}
}
}
// Calculate maximum bitonic sum using left and right sum.
for (int i = 0; i < n; ++i)
{
result = maxValue(result,
(sumRightToLeft[i] + sumLeftToRight[i] - arr[i]));
}
System.out.print("\n Given sequence : ");
display(arr, n);
System.out.print("\n Result : " + result + "");
}
public static void main(String[] args)
{
BitonicSequence task = new BitonicSequence();
// Array of integer elements
int[] arr1 = {
4 , 1 , 3 , 9 , 3 , -2 , 2 , 8 , 3 , 1 , 1 , 4 , 5
};
int[] arr2 = {
45 , 2 , 1 , 14 , 15 , 18 , 20 , 1 , -12 , 2 , 4
};
// Test A
int n = arr1.length;
// [1 + 3 + 9 + 8 + 5]
// maximum sum bitonic subsequence
// 26
task.maxSumBitonicSequence(arr1, n);
// Test B
n = arr2.length;
// [2 + 14 + 15 + 18 + 20 + 4]
// maximum sum bitonic subsequence
// 73
task.maxSumBitonicSequence(arr2, n);
}
}
Output
Given sequence : 4 1 3 9 3 -2 2 8 3 1 1 4 5
Result : 26
Given sequence : 45 2 1 14 15 18 20 1 -12 2 4
Result : 73
// Include header file
#include <iostream>
#include <limits.h>
using namespace std;
/*
C++ Program for
Find maximum sum bitonic sub sequence using dynamic programming
*/
class BitonicSequence
{
public:
// Function which is display array elements
void display(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
}
// Returns a max value of two integers
int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
void maxSumBitonicSequence(int arr[], int n)
{
// This is collects the sum of bitonic subsequence from left to right.
int sumLeftToRight[n];
// This is collects the sum of bitonic subsequence from right to left.
int sumRightToLeft[n];
// Initial value of result is minimum value.
int result = INT_MIN;
// Set initial value of sum
for (int i = 0; i < n; ++i)
{
sumLeftToRight[i] = arr[i];
sumRightToLeft[i] = arr[i];
}
// Calculate right to left maximum bitonic sum.
// This loop start with second last element and
// Execute until the its value is not -1.
for (int i = n - 2; i >= 0; --i)
{
// This loop start with last element and execute
// until the its value is greater than [i].
for (int j = n - 1; j > i; --j)
{
if (arr[i] > arr[j] &&
(sumRightToLeft[i] < sumRightToLeft[j] + arr[i]))
{
// Update sum value
sumRightToLeft[i] = sumRightToLeft[j] + arr[i];
}
}
}
// Calculate left to right maximum bitonic sum
for (int i = 1; i < n; ++i)
{
for (int j = 0; j < i; ++j)
{
if (arr[i] > arr[j] &&
(sumLeftToRight[i] < sumLeftToRight[j] + arr[i]))
{
// Update sum value
sumLeftToRight[i] = sumLeftToRight[j] + arr[i];
}
}
}
// Calculate maximum bitonic sum using left and right sum.
for (int i = 0; i < n; ++i)
{
result = this->maxValue(result,
(sumRightToLeft[i] + sumLeftToRight[i] - arr[i]));
}
cout << "\n Given sequence : ";
this->display(arr, n);
cout << "\n Result : " << result << "";
}
};
int main()
{
BitonicSequence *task = new BitonicSequence();
// Array of integer elements
int arr1[] = {
4 , 1 , 3 , 9 , 3 , -2 , 2 , 8 , 3 , 1 , 1 , 4 , 5
};
int arr2[] = {
45 , 2 , 1 , 14 , 15 , 18 , 20 , 1 , -12 , 2 , 4
};
// Test A
int n = sizeof(arr1) / sizeof(arr1[0]);
// [1 + 3 + 9 + 8 + 5]
// maximum sum bitonic subsequence
// 26
task->maxSumBitonicSequence(arr1, n);
// Test B
n = sizeof(arr2) / sizeof(arr2[0]);
// [2 + 14 + 15 + 18 + 20 + 4]
// maximum sum bitonic subsequence
// 73
task->maxSumBitonicSequence(arr2, n);
return 0;
}
Output
Given sequence : 4 1 3 9 3 -2 2 8 3 1 1 4 5
Result : 26
Given sequence : 45 2 1 14 15 18 20 1 -12 2 4
Result : 73
// Include namespace system
using System;
/*
Csharp Program for
Find maximum sum bitonic sub sequence using dynamic programming
*/
public class BitonicSequence
{
// Function which is display array elements
public void display(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
}
// Returns a max value of two integers
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public void maxSumBitonicSequence(int[] arr, int n)
{
// This is collects the sum of bitonic subsequence from left to right.
int[] sumLeftToRight = new int[n];
// This is collects the sum of bitonic subsequence from right to left.
int[] sumRightToLeft = new int[n];
// Initial value of result is minimum value.
int result = int.MinValue;
// Set initial value of sum
for (int i = 0; i < n; ++i)
{
sumLeftToRight[i] = arr[i];
sumRightToLeft[i] = arr[i];
}
// Calculate right to left maximum bitonic sum.
// This loop start with second last element and
// Execute until the its value is not -1.
for (int i = n - 2; i >= 0; --i)
{
// This loop start with last element and execute
// until the its value is greater than [i].
for (int j = n - 1; j > i; --j)
{
if (arr[i] > arr[j] &&
(sumRightToLeft[i] < sumRightToLeft[j] + arr[i]))
{
// Update sum value
sumRightToLeft[i] = sumRightToLeft[j] + arr[i];
}
}
}
// Calculate left to right maximum bitonic sum
for (int i = 1; i < n; ++i)
{
for (int j = 0; j < i; ++j)
{
if (arr[i] > arr[j] &&
(sumLeftToRight[i] < sumLeftToRight[j] + arr[i]))
{
// Update sum value
sumLeftToRight[i] = sumLeftToRight[j] + arr[i];
}
}
}
// Calculate maximum bitonic sum using left and right sum.
for (int i = 0; i < n; ++i)
{
result = this.maxValue(result,
(sumRightToLeft[i] + sumLeftToRight[i] - arr[i]));
}
Console.Write("\n Given sequence : ");
this.display(arr, n);
Console.Write("\n Result : " + result + "");
}
public static void Main(String[] args)
{
BitonicSequence task = new BitonicSequence();
// Array of integer elements
int[] arr1 = {
4 , 1 , 3 , 9 , 3 , -2 , 2 , 8 , 3 , 1 , 1 , 4 , 5
};
int[] arr2 = {
45 , 2 , 1 , 14 , 15 , 18 , 20 , 1 , -12 , 2 , 4
};
// Test A
int n = arr1.Length;
// [1 + 3 + 9 + 8 + 5]
// maximum sum bitonic subsequence
// 26
task.maxSumBitonicSequence(arr1, n);
// Test B
n = arr2.Length;
// [2 + 14 + 15 + 18 + 20 + 4]
// maximum sum bitonic subsequence
// 73
task.maxSumBitonicSequence(arr2, n);
}
}
Output
Given sequence : 4 1 3 9 3 -2 2 8 3 1 1 4 5
Result : 26
Given sequence : 45 2 1 14 15 18 20 1 -12 2 4
Result : 73
package main
import "math"
import "fmt"
/*
Go Program for
Find maximum sum bitonic sub sequence using dynamic programming
*/
// Function which is display array elements
func display(arr[] int, n int) {
for i := 0 ; i < n ; i++ {
fmt.Print(" ", arr[i])
}
}
// Returns a max value of two integers
func maxValue(a, b int) int {
if a > b {
return a
}
return b
}
func maxSumBitonicSequence(arr[] int, n int) {
// This is collects the sum of bitonic subsequence from left to right.
var sumLeftToRight = make([] int, n)
// This is collects the sum of bitonic subsequence from right to left.
var sumRightToLeft = make([] int, n)
// Initial value of result is minimum value.
var result int = math.MinInt64
// Set initial value of sum
for i := 0 ; i < n ; i++ {
sumLeftToRight[i] = arr[i]
sumRightToLeft[i] = arr[i]
}
// Calculate right to left maximum bitonic sum.
// This loop start with second last element and
// Execute until the its value is not -1.
for i := n - 2 ; i >= 0 ; i-- {
// This loop start with last element and execute
// until the its value is greater than [i].
for j := n - 1 ; j > i ; j-- {
if arr[i] > arr[j] && (sumRightToLeft[i] < sumRightToLeft[j] + arr[i]) {
// Update sum value
sumRightToLeft[i] = sumRightToLeft[j] + arr[i]
}
}
}
// Calculate left to right maximum bitonic sum
for i := 1 ; i < n ; i++ {
for j := 0 ; j < i ; j++ {
if arr[i] > arr[j] && (sumLeftToRight[i] < sumLeftToRight[j] + arr[i]) {
// Update sum value
sumLeftToRight[i] = sumLeftToRight[j] + arr[i]
}
}
}
// Calculate maximum bitonic sum using left and right sum.
for i := 0 ; i < n ; i++ {
result = maxValue(result,
(sumRightToLeft[i] + sumLeftToRight[i] - arr[i]))
}
fmt.Print("\n Given sequence : ")
display(arr, n)
fmt.Print("\n Result : ", result, "")
}
func main() {
// Array of integer elements
var arr1 = [] int {4, 1, 3, 9, 3, -2, 2, 8, 3, 1 , 1, 4, 5}
var arr2 = [] int {45, 2, 1, 14, 15, 18 , 20, 1, -12, 2, 4}
// Test A
var n int = len(arr1)
// [1 + 3 + 9 + 8 + 5]
// maximum sum bitonic subsequence
// 26
maxSumBitonicSequence(arr1, n)
// Test B
n = len(arr2)
// [2 + 14 + 15 + 18 + 20 + 4]
// maximum sum bitonic subsequence
// 73
maxSumBitonicSequence(arr2, n)
}
Output
Given sequence : 4 1 3 9 3 -2 2 8 3 1 1 4 5
Result : 26
Given sequence : 45 2 1 14 15 18 20 1 -12 2 4
Result : 73
<?php
/*
Php Program for
Find maximum sum bitonic sub sequence using dynamic programming
*/
class BitonicSequence
{
// Function which is display array elements
public function display($arr, $n)
{
for ($i = 0; $i < $n; ++$i)
{
echo(" ".$arr[$i]);
}
}
// Returns a max value of two integers
public function maxValue($a, $b)
{
if ($a > $b)
{
return $a;
}
return $b;
}
public function maxSumBitonicSequence($arr, $n)
{
// This is collects the sum of bitonic subsequence from left to right.
$sumLeftToRight = array_fill(0, $n, 0);
// This is collects the sum of bitonic subsequence from right to left.
$sumRightToLeft = array_fill(0, $n, 0);
// Initial value of result is minimum value.
$result = -PHP_INT_MAX;
// Set initial value of sum
for ($i = 0; $i < $n; ++$i)
{
$sumLeftToRight[$i] = $arr[$i];
$sumRightToLeft[$i] = $arr[$i];
}
// Calculate right to left maximum bitonic sum.
// This loop start with second last element and
// Execute until the its value is not -1.
for ($i = $n - 2; $i >= 0; --$i)
{
// This loop start with last element and execute
// until the its value is greater than [i].
for ($j = $n - 1; $j > $i; --$j)
{
if ($arr[$i] > $arr[$j] && ($sumRightToLeft[$i] < $sumRightToLeft[$j] + $arr[$i]))
{
// Update sum value
$sumRightToLeft[$i] = $sumRightToLeft[$j] + $arr[$i];
}
}
}
// Calculate left to right maximum bitonic sum
for ($i = 1; $i < $n; ++$i)
{
for ($j = 0; $j < $i; ++$j)
{
if ($arr[$i] > $arr[$j] && ($sumLeftToRight[$i] < $sumLeftToRight[$j] + $arr[$i]))
{
// Update sum value
$sumLeftToRight[$i] = $sumLeftToRight[$j] + $arr[$i];
}
}
}
// Calculate maximum bitonic sum using left and right sum.
for ($i = 0; $i < $n; ++$i)
{
$result = $this->maxValue($result, ($sumRightToLeft[$i] + $sumLeftToRight[$i] - $arr[$i]));
}
echo("\n Given sequence : ");
$this->display($arr, $n);
echo("\n Result : ".$result.
"");
}
}
function main()
{
$task = new BitonicSequence();
// Array of integer elements
$arr1 = array(4, 1, 3, 9, 3, -2, 2, 8, 3, 1, 1, 4, 5);
$arr2 = array(45, 2, 1, 14, 15, 18, 20, 1, -12, 2, 4);
// Test A
$n = count($arr1);
// [1 + 3 + 9 + 8 + 5]
// maximum sum bitonic subsequence
// 26
$task->maxSumBitonicSequence($arr1, $n);
// Test B
$n = count($arr2);
// [2 + 14 + 15 + 18 + 20 + 4]
// maximum sum bitonic subsequence
// 73
$task->maxSumBitonicSequence($arr2, $n);
}
main();
Output
Given sequence : 4 1 3 9 3 -2 2 8 3 1 1 4 5
Result : 26
Given sequence : 45 2 1 14 15 18 20 1 -12 2 4
Result : 73
/*
Node JS Program for
Find maximum sum bitonic sub sequence using dynamic programming
*/
class BitonicSequence
{
// Function which is display array elements
display(arr, n)
{
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + arr[i]);
}
}
// Returns a max value of two integers
maxValue(a, b)
{
if (a > b)
{
return a;
}
return b;
}
maxSumBitonicSequence(arr, n)
{
// This is collects the sum of bitonic subsequence from left to right.
var sumLeftToRight = Array(n).fill(0);
// This is collects the sum of bitonic subsequence from right to left.
var sumRightToLeft = Array(n).fill(0);
// Initial value of result is minimum value.
var result = -Number.MAX_VALUE;
// Set initial value of sum
for (var i = 0; i < n; ++i)
{
sumLeftToRight[i] = arr[i];
sumRightToLeft[i] = arr[i];
}
// Calculate right to left maximum bitonic sum.
// This loop start with second last element and
// Execute until the its value is not -1.
for (var i = n - 2; i >= 0; --i)
{
// This loop start with last element and execute
// until the its value is greater than [i].
for (var j = n - 1; j > i; --j)
{
if (arr[i] > arr[j] &&
(sumRightToLeft[i] < sumRightToLeft[j] + arr[i]))
{
// Update sum value
sumRightToLeft[i] = sumRightToLeft[j] + arr[i];
}
}
}
// Calculate left to right maximum bitonic sum
for (var i = 1; i < n; ++i)
{
for (var j = 0; j < i; ++j)
{
if (arr[i] > arr[j] &&
(sumLeftToRight[i] < sumLeftToRight[j] + arr[i]))
{
// Update sum value
sumLeftToRight[i] = sumLeftToRight[j] + arr[i];
}
}
}
// Calculate maximum bitonic sum using left and right sum.
for (var i = 0; i < n; ++i)
{
result = this.maxValue(result,
(sumRightToLeft[i] + sumLeftToRight[i] - arr[i]));
}
process.stdout.write("\n Given sequence : ");
this.display(arr, n);
process.stdout.write("\n Result : " + result + "");
}
}
function main()
{
var task = new BitonicSequence();
// Array of integer elements
var arr1 = [4, 1, 3, 9, 3, -2, 2, 8, 3, 1, 1, 4, 5];
var arr2 = [45, 2, 1, 14, 15, 18, 20, 1, -12, 2, 4];
// Test A
var n = arr1.length;
// [1 + 3 + 9 + 8 + 5]
// maximum sum bitonic subsequence
// 26
task.maxSumBitonicSequence(arr1, n);
// Test B
n = arr2.length;
// [2 + 14 + 15 + 18 + 20 + 4]
// maximum sum bitonic subsequence
// 73
task.maxSumBitonicSequence(arr2, n);
}
main();
Output
Given sequence : 4 1 3 9 3 -2 2 8 3 1 1 4 5
Result : 26
Given sequence : 45 2 1 14 15 18 20 1 -12 2 4
Result : 73
import sys
# Python 3 Program for
# Find maximum sum bitonic sub sequence using dynamic programming
class BitonicSequence :
# Function which is display list elements
def display(self, arr, n) :
i = 0
while (i < n) :
print(" ", arr[i], end = "")
i += 1
# Returns a max value of two integers
def maxValue(self, a, b) :
if (a > b) :
return a
return b
def maxSumBitonicSequence(self, arr, n) :
# This is collects the sum of bitonic subsequence from left to right.
sumLeftToRight = [0] * (n)
# This is collects the sum of bitonic subsequence from right to left.
sumRightToLeft = [0] * (n)
# Initial value of result is minimum value.
result = -sys.maxsize
i = 0
# Set initial value of sum
while (i < n) :
sumLeftToRight[i] = arr[i]
sumRightToLeft[i] = arr[i]
i += 1
i = n - 2
# Calculate right to left maximum bitonic sum.
# This loop start with second last element and
# Execute until the its value is not -1.
while (i >= 0) :
j = n - 1
# This loop start with last element and execute
# until the its value is greater than [i].
while (j > i) :
if (arr[i] > arr[j] and(sumRightToLeft[i] < sumRightToLeft[j] + arr[i])) :
# Update sum value
sumRightToLeft[i] = sumRightToLeft[j] + arr[i]
j -= 1
i -= 1
i = 1
# Calculate left to right maximum bitonic sum
while (i < n) :
j = 0
while (j < i) :
if (arr[i] > arr[j] and(sumLeftToRight[i] < sumLeftToRight[j] + arr[i])) :
# Update sum value
sumLeftToRight[i] = sumLeftToRight[j] + arr[i]
j += 1
i += 1
i = 0
# Calculate maximum bitonic sum using left and right sum.
while (i < n) :
result = self.maxValue(result, (sumRightToLeft[i] + sumLeftToRight[i] - arr[i]))
i += 1
print("\n Given sequence : ", end = "")
self.display(arr, n)
print("\n Result : ", result ,"", end = "")
def main() :
task = BitonicSequence()
# Array of integer elements
arr1 = [4, 1, 3, 9, 3, -2, 2, 8, 3, 1, 1, 4, 5]
arr2 = [45, 2, 1, 14, 15, 18, 20, 1, -12, 2, 4]
# Test A
n = len(arr1)
# [1 + 3 + 9 + 8 + 5]
# maximum sum bitonic subsequence
# 26
task.maxSumBitonicSequence(arr1, n)
# Test B
n = len(arr2)
# [2 + 14 + 15 + 18 + 20 + 4]
# maximum sum bitonic subsequence
# 73
task.maxSumBitonicSequence(arr2, n)
if __name__ == "__main__": main()
Output
Given sequence : 4 1 3 9 3 -2 2 8 3 1 1 4 5
Result : 26
Given sequence : 45 2 1 14 15 18 20 1 -12 2 4
Result : 73
# Ruby Program for
# Find maximum sum bitonic sub sequence using dynamic programming
class BitonicSequence
# Function which is display array elements
def display(arr, n)
i = 0
while (i < n)
print(" ", arr[i])
i += 1
end
end
# Returns a max value of two integers
def maxValue(a, b)
if (a > b)
return a
end
return b
end
def maxSumBitonicSequence(arr, n)
# This is collects the sum of bitonic subsequence from left to right.
sumLeftToRight = Array.new(n) {0}
# This is collects the sum of bitonic subsequence from right to left.
sumRightToLeft = Array.new(n) {0}
# Initial value of result is minimum value.
result = -(2 ** (0. size * 8 - 2))
i = 0
# Set initial value of sum
while (i < n)
sumLeftToRight[i] = arr[i]
sumRightToLeft[i] = arr[i]
i += 1
end
i = n - 2
# Calculate right to left maximum bitonic sum.
# This loop start with second last element and
# Execute until the its value is not -1.
while (i >= 0)
j = n - 1
# This loop start with last element and execute
# until the its value is greater than [i].
while (j > i)
if (arr[i] > arr[j] &&
(sumRightToLeft[i] < sumRightToLeft[j] + arr[i]))
# Update sum value
sumRightToLeft[i] = sumRightToLeft[j] + arr[i]
end
j -= 1
end
i -= 1
end
i = 1
# Calculate left to right maximum bitonic sum
while (i < n)
j = 0
while (j < i)
if (arr[i] > arr[j] &&
(sumLeftToRight[i] < sumLeftToRight[j] + arr[i]))
# Update sum value
sumLeftToRight[i] = sumLeftToRight[j] + arr[i]
end
j += 1
end
i += 1
end
i = 0
# Calculate maximum bitonic sum using left and right sum.
while (i < n)
result = self.maxValue(result,
(sumRightToLeft[i] + sumLeftToRight[i] - arr[i]))
i += 1
end
print("\n Given sequence : ")
self.display(arr, n)
print("\n Result : ", result ,"")
end
end
def main()
task = BitonicSequence.new()
# Array of integer elements
arr1 = [4, 1, 3, 9, 3, -2, 2, 8, 3, 1, 1, 4, 5]
arr2 = [45, 2, 1, 14, 15, 18, 20, 1, -12, 2, 4]
# Test A
n = arr1.length
# [1 + 3 + 9 + 8 + 5]
# maximum sum bitonic subsequence
# 26
task.maxSumBitonicSequence(arr1, n)
# Test B
n = arr2.length
# [2 + 14 + 15 + 18 + 20 + 4]
# maximum sum bitonic subsequence
# 73
task.maxSumBitonicSequence(arr2, n)
end
main()
Output
Given sequence : 4 1 3 9 3 -2 2 8 3 1 1 4 5
Result : 26
Given sequence : 45 2 1 14 15 18 20 1 -12 2 4
Result : 73
/*
Scala Program for
Find maximum sum bitonic sub sequence using dynamic programming
*/
class BitonicSequence()
{
// Function which is display array elements
def display(arr: Array[Int], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print(" " + arr(i));
i += 1;
}
}
// Returns a max value of two integers
def maxValue(a: Int, b: Int): Int = {
if (a > b)
{
return a;
}
return b;
}
def maxSumBitonicSequence(arr: Array[Int], n: Int): Unit = {
// This is collects the sum of bitonic subsequence from left to right.
var sumLeftToRight: Array[Int] = Array.fill[Int](n)(0);
// This is collects the sum of bitonic subsequence from right to left.
var sumRightToLeft: Array[Int] = Array.fill[Int](n)(0);
// Initial value of result is minimum value.
var result: Int = Int.MinValue;
var i: Int = 0;
// Set initial value of sum
while (i < n)
{
sumLeftToRight(i) = arr(i);
sumRightToLeft(i) = arr(i);
i += 1;
}
i = n - 2;
// Calculate right to left maximum bitonic sum.
// This loop start with second last element and
// Execute until the its value is not -1.
while (i >= 0)
{
var j: Int = n - 1;
// This loop start with last element and execute
// until the its value is greater than [i].
while (j > i)
{
if (arr(i) > arr(j) &&
(sumRightToLeft(i) < sumRightToLeft(j) + arr(i)))
{
// Update sum value
sumRightToLeft(i) = sumRightToLeft(j) + arr(i);
}
j -= 1;
}
i -= 1;
}
i = 1;
// Calculate left to right maximum bitonic sum
while (i < n)
{
var j: Int = 0;
while (j < i)
{
if (arr(i) > arr(j) &&
(sumLeftToRight(i) < sumLeftToRight(j) + arr(i)))
{
// Update sum value
sumLeftToRight(i) = sumLeftToRight(j) + arr(i);
}
j += 1;
}
i += 1;
}
i = 0;
// Calculate maximum bitonic sum using left and right sum.
while (i < n)
{
result = maxValue(result,
(sumRightToLeft(i) + sumLeftToRight(i) - arr(i)));
i += 1;
}
print("\n Given sequence : ");
display(arr, n);
print("\n Result : " + result + "");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: BitonicSequence = new BitonicSequence();
// Array of integer elements
var arr1: Array[Int] = Array(4, 1, 3, 9, 3, -2, 2, 8, 3, 1, 1, 4, 5);
var arr2: Array[Int] = Array(45, 2, 1, 14, 15, 18, 20, 1, -12, 2, 4);
// Test A
var n: Int = arr1.length;
// [1 + 3 + 9 + 8 + 5]
// maximum sum bitonic subsequence
// 26
task.maxSumBitonicSequence(arr1, n);
// Test B
n = arr2.length;
// [2 + 14 + 15 + 18 + 20 + 4]
// maximum sum bitonic subsequence
// 73
task.maxSumBitonicSequence(arr2, n);
}
}
Output
Given sequence : 4 1 3 9 3 -2 2 8 3 1 1 4 5
Result : 26
Given sequence : 45 2 1 14 15 18 20 1 -12 2 4
Result : 73
import Foundation;
/*
Swift 4 Program for
Find maximum sum bitonic sub sequence using dynamic programming
*/
class BitonicSequence
{
// Function which is display array elements
func display(_ arr: [Int], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
}
// Returns a max value of two integers
func maxValue(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
return a;
}
return b;
}
func maxSumBitonicSequence(_ arr: [Int], _ n: Int)
{
// This is collects the sum of bitonic subsequence from left to right.
var sumLeftToRight: [Int] = Array(repeating: 0, count: n);
// This is collects the sum of bitonic subsequence from right to left.
var sumRightToLeft: [Int] = Array(repeating: 0, count: n);
// Initial value of result is minimum value.
var result: Int = Int.min;
var i: Int = 0;
// Set initial value of sum
while (i < n)
{
sumLeftToRight[i] = arr[i];
sumRightToLeft[i] = arr[i];
i += 1;
}
i = n - 2;
// Calculate right to left maximum bitonic sum.
// This loop start with second last element and
// Execute until the its value is not -1.
while (i >= 0)
{
var j: Int = n - 1;
// This loop start with last element and execute
// until the its value is greater than [i].
while (j > i)
{
if (arr[i] > arr[j] &&
(sumRightToLeft[i] < sumRightToLeft[j] + arr[i]))
{
// Update sum value
sumRightToLeft[i] = sumRightToLeft[j] + arr[i];
}
j -= 1;
}
i -= 1;
}
i = 1;
// Calculate left to right maximum bitonic sum
while (i < n)
{
var j: Int = 0;
while (j < i)
{
if (arr[i] > arr[j] &&
(sumLeftToRight[i] < sumLeftToRight[j] + arr[i]))
{
// Update sum value
sumLeftToRight[i] = sumLeftToRight[j] + arr[i];
}
j += 1;
}
i += 1;
}
i = 0;
// Calculate maximum bitonic sum using left and right sum.
while (i < n)
{
result = self.maxValue(result,
(sumRightToLeft[i] + sumLeftToRight[i] - arr[i]));
i += 1;
}
print("\n Given sequence : ", terminator: "");
self.display(arr, n);
print("\n Result : ", result ,"", terminator: "");
}
}
func main()
{
let task: BitonicSequence = BitonicSequence();
// Array of integer elements
let arr1: [Int] = [4, 1, 3, 9, 3, -2, 2, 8, 3, 1, 1, 4, 5];
let arr2: [Int] = [45, 2, 1, 14, 15, 18, 20, 1, -12, 2, 4];
// Test A
var n: Int = arr1.count;
// [1 + 3 + 9 + 8 + 5]
// maximum sum bitonic subsequence
// 26
task.maxSumBitonicSequence(arr1, n);
// Test B
n = arr2.count;
// [2 + 14 + 15 + 18 + 20 + 4]
// maximum sum bitonic subsequence
// 73
task.maxSumBitonicSequence(arr2, n);
}
main();
Output
Given sequence : 4 1 3 9 3 -2 2 8 3 1 1 4 5
Result : 26
Given sequence : 45 2 1 14 15 18 20 1 -12 2 4
Result : 73
/*
Kotlin Program for
Find maximum sum bitonic sub sequence using dynamic programming
*/
class BitonicSequence
{
// Function which is display array elements
fun display(arr: Array < Int > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print(" " + arr[i]);
i += 1;
}
}
// Returns a max value of two integers
fun maxValue(a: Int, b: Int): Int
{
if (a > b)
{
return a;
}
return b;
}
fun maxSumBitonicSequence(arr: Array < Int > , n: Int): Unit
{
// This is collects the sum of bitonic subsequence from left to right.
var sumLeftToRight: Array < Int > = Array(n)
{
0
};
// This is collects the sum of bitonic subsequence from right to left.
var sumRightToLeft: Array < Int > = Array(n)
{
0
};
// Initial value of result is minimum value.
var result: Int = Int.MIN_VALUE;
var i: Int = 0;
// Set initial value of sum
while (i < n)
{
sumLeftToRight[i] = arr[i];
sumRightToLeft[i] = arr[i];
i += 1;
}
i = n - 2;
// Calculate right to left maximum bitonic sum.
// This loop start with second last element and
// Execute until the its value is not -1.
while (i >= 0)
{
var j: Int = n - 1;
// This loop start with last element and execute
// until the its value is greater than [i].
while (j > i)
{
if (arr[i] > arr[j] &&
(sumRightToLeft[i] < sumRightToLeft[j] + arr[i]))
{
// Update sum value
sumRightToLeft[i] = sumRightToLeft[j] + arr[i];
}
j -= 1;
}
i -= 1;
}
i = 1;
// Calculate left to right maximum bitonic sum
while (i < n)
{
var j: Int = 0;
while (j < i)
{
if (arr[i] > arr[j] &&
(sumLeftToRight[i] < sumLeftToRight[j] + arr[i]))
{
// Update sum value
sumLeftToRight[i] = sumLeftToRight[j] + arr[i];
}
j += 1;
}
i += 1;
}
i = 0;
// Calculate maximum bitonic sum using left and right sum.
while (i < n)
{
result = this.maxValue(result,
(sumRightToLeft[i] + sumLeftToRight[i] - arr[i]));
i += 1;
}
print("\n Given sequence : ");
this.display(arr, n);
print("\n Result : " + result + "");
}
}
fun main(args: Array < String > ): Unit
{
val task: BitonicSequence = BitonicSequence();
// Array of integer elements
val arr1: Array < Int > = arrayOf(4, 1, 3, 9, 3, -2, 2, 8, 3, 1, 1, 4, 5);
val arr2: Array < Int > = arrayOf(45, 2, 1, 14, 15, 18, 20, 1, -12, 2, 4);
// Test A
var n: Int = arr1.count();
// [1 + 3 + 9 + 8 + 5]
// maximum sum bitonic subsequence
// 26
task.maxSumBitonicSequence(arr1, n);
// Test B
n = arr2.count();
// [2 + 14 + 15 + 18 + 20 + 4]
// maximum sum bitonic subsequence
// 73
task.maxSumBitonicSequence(arr2, n);
}
Output
Given sequence : 4 1 3 9 3 -2 2 8 3 1 1 4 5
Result : 26
Given sequence : 45 2 1 14 15 18 20 1 -12 2 4
Result : 73
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