Posted on by Kalkicode
Code Dynamic Programming

Find maximum sum bitonic sub sequence using dynamic programming

Dynamic programming is a powerful technique used to solve optimization problems by breaking them down into overlapping subproblems and solving them in a bottom-up manner. The maximum sum bitonic subsequence problem is one such problem that can be efficiently solved using dynamic programming. Given an array of integers, the task is to find the maximum sum of a subsequence that is bitonic, i.e., it first increases and then decreases.

Problem Statement

Given an array of integers, we need to find the maximum sum of a bitonic subsequence. A bitonic subsequence is a subsequence that first increases and then decreases. The subsequence can be non-contiguous, meaning the selected elements can have gaps in between as long as they maintain the bitonic property.

Pseudocode Algorithm

Let's go through the step-by-step algorithm to solve the maximum sum bitonic subsequence problem using dynamic programming:

  1. Define a function, maxSumBitonicSequence, which takes the input array arr and its length n.
  2. Create two arrays, sumLeftToRight and sumRightToLeft, of size n to store the maximum sum of bitonic subsequences from left to right and right to left, respectively.
  3. Initialize each element of sumLeftToRight and sumRightToLeft with the corresponding element of arr since each element itself forms a bitonic subsequence.
  4. Calculate the maximum sum of bitonic subsequences from right to left by iterating from the second last element of arr to the first element:
    • For each element arr[i], compare it with the elements on its right.
    • If arr[i] is greater than an element on its right and the sum of the bitonic subsequence ending at arr[i] is less than the sum of the bitonic subsequence ending at that element, update the sum.
  5. Calculate the maximum sum of bitonic subsequences from left to right by iterating from the second element to the last element of arr:
    • For each element arr[i], compare it with the elements on its left.
    • If arr[i] is greater than an element on its left and the sum of the bitonic subsequence starting at arr[i] is less than the sum of the bitonic subsequence starting at that element, update the sum.
  6. Calculate the maximum bitonic sum by iterating through the array and finding the maximum value of sumRightToLeft[i] + sumLeftToRight[i] - arr[i] for each element.
  7. Print the given sequence and the result, which represents the maximum sum bitonic subsequence.

Code Solution

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

Resultant Output Explanation

Let's analyze the output of the given example:

Test A

The given sequence is 4 1 3 9 3 -2 2 8 3 1 1 4 5. The maximum sum bitonic subsequence is 1 + 3 + 9 + 8 + 5 = 26. Therefore, the result is 26.

Test B

The given sequence is 45 2 1 14 15 18 20 1 -12 2 4. The maximum sum bitonic subsequence is 2 + 14 + 15 + 18 + 20 + 4 = 73. Therefore, the result is 73.

By using dynamic programming, we can efficiently solve the maximum sum bitonic subsequence problem and obtain the desired results.

Time Complexity

The time complexity of the provided solution is O(n^2), where n is the length of the input array. This is because we have two nested loops to calculate the maximum sum bitonic subsequences from left to right and right to left, respectively. The third loop iterates through the array to find the maximum bitonic sum. Therefore, the overall time complexity is quadratic.

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





Categories
Relative Post