Skip to main content

Maximum sum bitonic subarray using dynamic programming

Here given code implementation process.

// C Program
// Maximum sum bitonic subarray 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 maxSumBitonicSubArray(int arr[], int n)
{
	if (n <= 0)
	{
		return;
	}
	// This is collects the sum of bitonic increasing 
	// subarry from left to right.
	int increasingSum[n];
	// This is collects the sum of bitonic decreasing 
	// subarry from right to left.
	int decreasingSum[n];
	// Assign first element value
	increasingSum[0] = arr[0];
	// Calculate increasing sum from left to right
	for (int i = 1; i < n; ++i)
	{
		if (arr[i] > arr[i - 1])
		{
			increasingSum[i] = increasingSum[i - 1] + arr[i];
		}
		else
		{
			increasingSum[i] = arr[i];
		}
	}
	// Assign last element value
	decreasingSum[n - 1] = arr[n - 1];
	// Calculate decreasing sum from right to left
	for (int i = n - 2; i >= 0; --i)
	{
		if (arr[i] > arr[i + 1])
		{
			decreasingSum[i] = decreasingSum[i + 1] + arr[i];
		}
		else
		{
			decreasingSum[i] = arr[i];
		}
	}
	// Initial value of result is minimum value.
	int result = INT_MIN;
	// Calcuate max sum bitonic subarray
	for (int i = 0; i < n; i++)
	{
		result = maxValue(result, 
                 increasingSum[i] + decreasingSum[i] - arr[i]);
	}
	printf("\n Given sequence : ");
	display(arr, n);
	printf("\n Result : %d", result);
}
int main()
{
	// Array of positive integer elements
	int arr1[] = {
		1 , 2 , 1 , 1 , 5 , 3 , 1 , 5 , 2 , 1
	};
	int arr2[] = {
		1 , 3 , 4 , 1 , 3 , 2 , 1
	};
	// Test A
	int n = sizeof(arr1) / sizeof(arr1[0]);
	// [1 + 5 + 3 + 1] 
	// maximum sum bitonic subarray 
	// 10
	maxSumBitonicSubArray(arr1, n);
	// Test B
	n = sizeof(arr2) / sizeof(arr2[0]);
	// [1 + 3 + 4 + 1] 
	// maximum sum bitonic subarray 
	// 9
	maxSumBitonicSubArray(arr2, n);
	return 0;
}

Output

 Given sequence : 1 2 1 1 5 3 1 5 2 1
 Result : 10
 Given sequence : 1 3 4 1 3 2 1
 Result : 9
/*
    Java Program for
    Maximum sum bitonic subarray using dynamic programming
*/
public class BitonicSubarray
{
    // 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 maxSumBitonicSubArray(int[] arr, int n)
    {
        if (n <= 0)
        {
            return;
        }
        // This is collects the sum of bitonic increasing 
        // subarry from left to right.
        int[] increasingSum = new int[n];
        // This is collects the sum of bitonic decreasing 
        // subarry from right to left.
        int[] decreasingSum = new int[n];
        // Assign first element value
        increasingSum[0] = arr[0];
        // Calculate increasing sum from left to right
        for (int i = 1; i < n; ++i)
        {
            if (arr[i] > arr[i - 1])
            {
                increasingSum[i] = increasingSum[i - 1] + arr[i];
            }
            else
            {
                increasingSum[i] = arr[i];
            }
        }
        // Assign last element value
        decreasingSum[n - 1] = arr[n - 1];
        // Calculate decreasing sum from right to left
        for (int i = n - 2; i >= 0; --i)
        {
            if (arr[i] > arr[i + 1])
            {
                decreasingSum[i] = decreasingSum[i + 1] + arr[i];
            }
            else
            {
                decreasingSum[i] = arr[i];
            }
        }
        // Initial value of result is minimum value.
        int result = Integer.MIN_VALUE;
        // Calcuate max sum bitonic subarray
        for (int i = 0; i < n; i++)
        {
            result = maxValue(result, 
                     increasingSum[i] + decreasingSum[i] - arr[i]);
        }
        System.out.print("\n Given sequence : ");
        display(arr, n);
        System.out.print("\n Result : " + result);
    }
    public static void main(String[] args)
    {
        BitonicSubarray task = new BitonicSubarray();
        // Array of positive integer elements
        int[] arr1 = {
            1 , 2 , 1 , 1 , 5 , 3 , 1 , 5 , 2 , 1
        };
        int[] arr2 = {
            1 , 3 , 4 , 1 , 3 , 2 , 1
        };
        // Test A
        int n = arr1.length;
        // [1 + 5 + 3 + 1] 
        // maximum sum bitonic subarray 
        // 10
        task.maxSumBitonicSubArray(arr1, n);
        // Test B
        n = arr2.length;
        // [1 + 3 + 4 + 1] 
        // maximum sum bitonic subarray 
        // 9
        task.maxSumBitonicSubArray(arr2, n);
    }
}

Output

 Given sequence :   1  2  1  1  5  3  1  5  2  1
 Result : 10
 Given sequence :   1  3  4  1  3  2  1
 Result : 9
// Include header file
#include <iostream>
#include <limits.h>
using namespace std;
/*
    C++ Program for
    Maximum sum bitonic subarray using dynamic programming
*/
class BitonicSubarray
{
	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 maxSumBitonicSubArray(int arr[], int n)
	{
		if (n <= 0)
		{
			return;
		}
		// This is collects the sum of bitonic increasing 
		// subarry from left to right.
		int increasingSum[n];
		// This is collects the sum of bitonic decreasing 
		// subarry from right to left.
		int decreasingSum[n];
		// Assign first element value
		increasingSum[0] = arr[0];
		// Calculate increasing sum from left to right
		for (int i = 1; i < n; ++i)
		{
			if (arr[i] > arr[i - 1])
			{
				increasingSum[i] = increasingSum[i - 1] + arr[i];
			}
			else
			{
				increasingSum[i] = arr[i];
			}
		}
		// Assign last element value
		decreasingSum[n - 1] = arr[n - 1];
		// Calculate decreasing sum from right to left
		for (int i = n - 2; i >= 0; --i)
		{
			if (arr[i] > arr[i + 1])
			{
				decreasingSum[i] = decreasingSum[i + 1] + arr[i];
			}
			else
			{
				decreasingSum[i] = arr[i];
			}
		}
		// Initial value of result is minimum value.
		int result = INT_MIN;
		// Calcuate max sum bitonic subarray
		for (int i = 0; i < n; i++)
		{
			result = this->maxValue(result, 
                     increasingSum[i] + decreasingSum[i] - arr[i]);
		}
		cout << "\n Given sequence : ";
		this->display(arr, n);
		cout << "\n Result : " << result;
	}
};
int main()
{
	BitonicSubarray *task = new BitonicSubarray();
	// Array of positive integer elements
	int arr1[] = {
		1 , 2 , 1 , 1 , 5 , 3 , 1 , 5 , 2 , 1
	};
	int arr2[] = {
		1 , 3 , 4 , 1 , 3 , 2 , 1
	};
	// Test A
	int n = sizeof(arr1) / sizeof(arr1[0]);
	// [1 + 5 + 3 + 1] 
	// maximum sum bitonic subarray 
	// 10
	task->maxSumBitonicSubArray(arr1, n);
	// Test B
	n = sizeof(arr2) / sizeof(arr2[0]);
	// [1 + 3 + 4 + 1] 
	// maximum sum bitonic subarray 
	// 9
	task->maxSumBitonicSubArray(arr2, n);
	return 0;
}

Output

 Given sequence :   1  2  1  1  5  3  1  5  2  1
 Result : 10
 Given sequence :   1  3  4  1  3  2  1
 Result : 9
// Include namespace system
using System;
/*
    Csharp Program for
    Maximum sum bitonic subarray using dynamic programming
*/
public class BitonicSubarray
{
	// 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 maxSumBitonicSubArray(int[] arr, int n)
	{
		if (n <= 0)
		{
			return;
		}
		// This is collects the sum of bitonic increasing 
		// subarry from left to right.
		int[] increasingSum = new int[n];
		// This is collects the sum of bitonic decreasing 
		// subarry from right to left.
		int[] decreasingSum = new int[n];
		// Assign first element value
		increasingSum[0] = arr[0];
		// Calculate increasing sum from left to right
		for (int i = 1; i < n; ++i)
		{
			if (arr[i] > arr[i - 1])
			{
				increasingSum[i] = increasingSum[i - 1] + arr[i];
			}
			else
			{
				increasingSum[i] = arr[i];
			}
		}
		// Assign last element value
		decreasingSum[n - 1] = arr[n - 1];
		// Calculate decreasing sum from right to left
		for (int i = n - 2; i >= 0; --i)
		{
			if (arr[i] > arr[i + 1])
			{
				decreasingSum[i] = decreasingSum[i + 1] + arr[i];
			}
			else
			{
				decreasingSum[i] = arr[i];
			}
		}
		// Initial value of result is minimum value.
		int result = int.MinValue;
		// Calcuate max sum bitonic subarray
		for (int i = 0; i < n; i++)
		{
			result = this.maxValue(result, 
                     increasingSum[i] + decreasingSum[i] - arr[i]);
		}
		Console.Write("\n Given sequence : ");
		this.display(arr, n);
		Console.Write("\n Result : " + result);
	}
	public static void Main(String[] args)
	{
		BitonicSubarray task = new BitonicSubarray();
		// Array of positive integer elements
		int[] arr1 = {
			1 , 2 , 1 , 1 , 5 , 3 , 1 , 5 , 2 , 1
		};
		int[] arr2 = {
			1 , 3 , 4 , 1 , 3 , 2 , 1
		};
		// Test A
		int n = arr1.Length;
		// [1 + 5 + 3 + 1] 
		// maximum sum bitonic subarray 
		// 10
		task.maxSumBitonicSubArray(arr1, n);
		// Test B
		n = arr2.Length;
		// [1 + 3 + 4 + 1] 
		// maximum sum bitonic subarray 
		// 9
		task.maxSumBitonicSubArray(arr2, n);
	}
}

Output

 Given sequence :   1  2  1  1  5  3  1  5  2  1
 Result : 10
 Given sequence :   1  3  4  1  3  2  1
 Result : 9
package main
import "math"
import "fmt"
/*
    Go Program for
    Maximum sum bitonic subarray 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 maxSumBitonicSubArray(arr[] int, n int) {
	if n <= 0 {
		return
	}
	// This is collects the sum of bitonic increasing 
	// subarry from left to right.
	var increasingSum = make([] int, n)
	// This is collects the sum of bitonic decreasing 
	// subarry from right to left.
	var decreasingSum = make([] int, n)
	// Assign first element value
	increasingSum[0] = arr[0]
	// Calculate increasing sum from left to right
	for i := 1 ; i < n ; i++ {
		if arr[i] > arr[i - 1] {
			increasingSum[i] = increasingSum[i - 1] + arr[i]
		} else {
			increasingSum[i] = arr[i]
		}
	}
	// Assign last element value
	decreasingSum[n - 1] = arr[n - 1]
	// Calculate decreasing sum from right to left
	for i := n - 2 ; i >= 0 ; i-- {
		if arr[i] > arr[i + 1] {
			decreasingSum[i] = decreasingSum[i + 1] + arr[i]
		} else {
			decreasingSum[i] = arr[i]
		}
	}
	// Initial value of result is minimum value.
	var result int = math.MinInt64
	// Calcuate max sum bitonic subarray
	for i := 0 ; i < n ; i++ {
		result = maxValue(result, 
				increasingSum[i] + decreasingSum[i] - arr[i])
	}
	fmt.Print("\n Given sequence : ")
	display(arr, n)
	fmt.Print("\n Result : ", result)
}
func main() {
	
	// Array of positive integer elements
	var arr1 = [] int { 1 , 2 , 1 , 1 , 5 , 3 , 1 , 5 , 2 , 1 }
	var arr2 = [] int { 1 , 3, 4, 1, 3, 2, 1 }
	// Test A
	var n int = len(arr1)
	// [1 + 5 + 3 + 1] 
	// maximum sum bitonic subarray 
	// 10
	maxSumBitonicSubArray(arr1, n)
	// Test B
	n = len(arr2)
	// [1 + 3 + 4 + 1] 
	// maximum sum bitonic subarray 
	// 9
	maxSumBitonicSubArray(arr2, n)
}

Output

 Given sequence :   1  2  1  1  5  3  1  5  2  1
 Result : 10
 Given sequence :   1  3  4  1  3  2  1
 Result : 9
<?php
/*
    Php Program for
    Maximum sum bitonic subarray using dynamic programming
*/
class BitonicSubarray
{
	// 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 maxSumBitonicSubArray($arr, $n)
	{
		if ($n <= 0)
		{
			return;
		}
		// This is collects the sum of bitonic increasing 
		// subarry from left to right.
		$increasingSum = array_fill(0, $n, 0);
		// This is collects the sum of bitonic decreasing 
		// subarry from right to left.
		$decreasingSum = array_fill(0, $n, 0);
		// Assign first element value
		$increasingSum[0] = $arr[0];
		// Calculate increasing sum from left to right
		for ($i = 1; $i < $n; ++$i)
		{
			if ($arr[$i] > $arr[$i - 1])
			{
				$increasingSum[$i] = $increasingSum[$i - 1] + $arr[$i];
			}
			else
			{
				$increasingSum[$i] = $arr[$i];
			}
		}
		// Assign last element value
		$decreasingSum[$n - 1] = $arr[$n - 1];
		// Calculate decreasing sum from right to left
		for ($i = $n - 2; $i >= 0; --$i)
		{
			if ($arr[$i] > $arr[$i + 1])
			{
				$decreasingSum[$i] = $decreasingSum[$i + 1] + $arr[$i];
			}
			else
			{
				$decreasingSum[$i] = $arr[$i];
			}
		}
		// Initial value of result is minimum value.
		$result = -PHP_INT_MAX;
		// Calcuate max sum bitonic subarray
		for ($i = 0; $i < $n; $i++)
		{
			$result = $this->maxValue($result, 
                    $increasingSum[$i] + $decreasingSum[$i] - $arr[$i]);
		}
		echo("\n Given sequence : ");
		$this->display($arr, $n);
		echo("\n Result : ".$result);
	}
}

function main()
{
	$task = new BitonicSubarray();
	// Array of positive integer elements
	$arr1 = array(1, 2, 1, 1, 5, 3, 1, 5, 2, 1);
	$arr2 = array(1, 3, 4, 1, 3, 2, 1);
	// Test A
	$n = count($arr1);
	// [1 + 5 + 3 + 1] 
	// maximum sum bitonic subarray 
	// 10
	$task->maxSumBitonicSubArray($arr1, $n);
	// Test B
	$n = count($arr2);
	// [1 + 3 + 4 + 1] 
	// maximum sum bitonic subarray 
	// 9
	$task->maxSumBitonicSubArray($arr2, $n);
}
main();

Output

 Given sequence :   1  2  1  1  5  3  1  5  2  1
 Result : 10
 Given sequence :   1  3  4  1  3  2  1
 Result : 9
/*
    Node JS Program for
    Maximum sum bitonic subarray using dynamic programming
*/
class BitonicSubarray
{
	// 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;
	}
	maxSumBitonicSubArray(arr, n)
	{
		if (n <= 0)
		{
			return;
		}
		// This is collects the sum of bitonic increasing 
		// subarry from left to right.
		var increasingSum = Array(n).fill(0);
		// This is collects the sum of bitonic decreasing 
		// subarry from right to left.
		var decreasingSum = Array(n).fill(0);
		// Assign first element value
		increasingSum[0] = arr[0];
		// Calculate increasing sum from left to right
		for (var i = 1; i < n; ++i)
		{
			if (arr[i] > arr[i - 1])
			{
				increasingSum[i] = increasingSum[i - 1] + arr[i];
			}
			else
			{
				increasingSum[i] = arr[i];
			}
		}
		// Assign last element value
		decreasingSum[n - 1] = arr[n - 1];
		// Calculate decreasing sum from right to left
		for (var i = n - 2; i >= 0; --i)
		{
			if (arr[i] > arr[i + 1])
			{
				decreasingSum[i] = decreasingSum[i + 1] + arr[i];
			}
			else
			{
				decreasingSum[i] = arr[i];
			}
		}
		// Initial value of result is minimum value.
		var result = -Number.MAX_VALUE;
		// Calcuate max sum bitonic subarray
		for (var i = 0; i < n; i++)
		{
			result = this.maxValue(result, 
                     increasingSum[i] + decreasingSum[i] - arr[i]);
		}
		process.stdout.write("\n Given sequence : ");
		this.display(arr, n);
		process.stdout.write("\n Result : " + result);
	}
}

function main()
{
	var task = new BitonicSubarray();
	// Array of positive integer elements
	var arr1 = [1, 2, 1, 1, 5, 3, 1, 5, 2, 1];
	var arr2 = [1, 3, 4, 1, 3, 2, 1];
	// Test A
	var n = arr1.length;
	// [1 + 5 + 3 + 1] 
	// maximum sum bitonic subarray 
	// 10
	task.maxSumBitonicSubArray(arr1, n);
	// Test B
	n = arr2.length;
	// [1 + 3 + 4 + 1] 
	// maximum sum bitonic subarray 
	// 9
	task.maxSumBitonicSubArray(arr2, n);
}
main();

Output

 Given sequence :   1  2  1  1  5  3  1  5  2  1
 Result : 10
 Given sequence :   1  3  4  1  3  2  1
 Result : 9
import sys
#    Python 3 Program for
#    Maximum sum bitonic subarray using dynamic programming
class BitonicSubarray :
	#  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 maxSumBitonicSubArray(self, arr, n) :
		if (n <= 0) :
			return
		
		#  This is collects the sum of bitonic increasing 
		#  subarry from left to right.
		increasingSum = [0] * (n)
		#  This is collects the sum of bitonic decreasing 
		#  subarry from right to left.
		decreasingSum = [0] * (n)
		#  Assign first element value
		increasingSum[0] = arr[0]
		i = 1
		#  Calculate increasing sum from left to right
		while (i < n) :
			if (arr[i] > arr[i - 1]) :
				increasingSum[i] = increasingSum[i - 1] + arr[i]
			else :
				increasingSum[i] = arr[i]
			
			i += 1
		
		#  Assign last element value
		decreasingSum[n - 1] = arr[n - 1]
		i = n - 2
		#  Calculate decreasing sum from right to left
		while (i >= 0) :
			if (arr[i] > arr[i + 1]) :
				decreasingSum[i] = decreasingSum[i + 1] + arr[i]
			else :
				decreasingSum[i] = arr[i]
			
			i -= 1
		
		#  Initial value of result is minimum value.
		result = -sys.maxsize
		i = 0
		#  Calcuate max sum bitonic sublist
		while (i < n) :
			result = self.maxValue(result, 
                     increasingSum[i] + decreasingSum[i] - arr[i])
			i += 1
		
		print("\n Given sequence : ", end = "")
		self.display(arr, n)
		print("\n Result : ", result, end = "")
	

def main() :
	task = BitonicSubarray()
	#  Array of positive integer elements
	arr1 = [1, 2, 1, 1, 5, 3, 1, 5, 2, 1]
	arr2 = [1, 3, 4, 1, 3, 2, 1]
	#  Test A
	n = len(arr1)
	#  [1 + 5 + 3 + 1] 
	#  maximum sum bitonic sublist 
	#  10
	task.maxSumBitonicSubArray(arr1, n)
	#  Test B
	n = len(arr2)
	#  [1 + 3 + 4 + 1] 
	#  maximum sum bitonic sublist 
	#  9
	task.maxSumBitonicSubArray(arr2, n)

if __name__ == "__main__": main()

Output

 Given sequence :    1   2   1   1   5   3   1   5   2   1
 Result :  10
 Given sequence :    1   3   4   1   3   2   1
 Result :  9
#    Ruby Program for
#    Maximum sum bitonic subarray using dynamic programming
class BitonicSubarray 
	#  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 maxSumBitonicSubArray(arr, n) 
		if (n <= 0) 
			return
		end

		#  This is collects the sum of bitonic increasing 
		#  subarry from left to right.
		increasingSum = Array.new(n) {0}
		#  This is collects the sum of bitonic decreasing 
		#  subarry from right to left.
		decreasingSum = Array.new(n) {0}
		#  Assign first element value
		increasingSum[0] = arr[0]
		i = 1
		#  Calculate increasing sum from left to right
		while (i < n) 
			if (arr[i] > arr[i - 1]) 
				increasingSum[i] = increasingSum[i - 1] + arr[i]
			else
 
				increasingSum[i] = arr[i]
			end

			i += 1
		end

		#  Assign last element value
		decreasingSum[n - 1] = arr[n - 1]
		i = n - 2
		#  Calculate decreasing sum from right to left
		while (i >= 0) 
			if (arr[i] > arr[i + 1]) 
				decreasingSum[i] = decreasingSum[i + 1] + arr[i]
			else
 
				decreasingSum[i] = arr[i]
			end

			i -= 1
		end

		#  Initial value of result is minimum value.
		result = -(2 ** (0. size * 8 - 2))
		i = 0
		#  Calcuate max sum bitonic subarray
		while (i < n) 
			result = self.maxValue(result, 
                     increasingSum[i] + decreasingSum[i] - arr[i])
			i += 1
		end

		print("\n Given sequence : ")
		self.display(arr, n)
		print("\n Result : ", result)
	end

end

def main() 
	task = BitonicSubarray.new()
	#  Array of positive integer elements
	arr1 = [1, 2, 1, 1, 5, 3, 1, 5, 2, 1]
	arr2 = [1, 3, 4, 1, 3, 2, 1]
	#  Test A
	n = arr1.length
	#  [1 + 5 + 3 + 1] 
	#  maximum sum bitonic subarray 
	#  10
	task.maxSumBitonicSubArray(arr1, n)
	#  Test B
	n = arr2.length
	#  [1 + 3 + 4 + 1] 
	#  maximum sum bitonic subarray 
	#  9
	task.maxSumBitonicSubArray(arr2, n)
end

main()

Output

 Given sequence :   1  2  1  1  5  3  1  5  2  1
 Result : 10
 Given sequence :   1  3  4  1  3  2  1
 Result : 9
/*
    Scala Program for
    Maximum sum bitonic subarray using dynamic programming
*/
class BitonicSubarray()
{
	// 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 maxSumBitonicSubArray(arr: Array[Int], n: Int): Unit = {
		if (n <= 0)
		{
			return;
		}
		// This is collects the sum of bitonic increasing 
		// subarry from left to right.
		var increasingSum: Array[Int] = Array.fill[Int](n)(0);
		// This is collects the sum of bitonic decreasing 
		// subarry from right to left.
		var decreasingSum: Array[Int] = Array.fill[Int](n)(0);
		// Assign first element value
		increasingSum(0) = arr(0);
		var i: Int = 1;
		// Calculate increasing sum from left to right
		while (i < n)
		{
			if (arr(i) > arr(i - 1))
			{
				increasingSum(i) = increasingSum(i - 1) + arr(i);
			}
			else
			{
				increasingSum(i) = arr(i);
			}
			i += 1;
		}
		// Assign last element value
		decreasingSum(n - 1) = arr(n - 1);
		i = n - 2;
		// Calculate decreasing sum from right to left
		while (i >= 0)
		{
			if (arr(i) > arr(i + 1))
			{
				decreasingSum(i) = decreasingSum(i + 1) + arr(i);
			}
			else
			{
				decreasingSum(i) = arr(i);
			}
			i -= 1;
		}
		// Initial value of result is minimum value.
		var result: Int = Int.MinValue;
		i = 0;
		// Calcuate max sum bitonic subarray
		while (i < n)
		{
			result = maxValue(result, 
                     increasingSum(i) + decreasingSum(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: BitonicSubarray = new BitonicSubarray();
		// Array of positive integer elements
		var arr1: Array[Int] = Array(1, 2, 1, 1, 5, 3, 1, 5, 2, 1);
		var arr2: Array[Int] = Array(1, 3, 4, 1, 3, 2, 1);
		// Test A
		var n: Int = arr1.length;
		// [1 + 5 + 3 + 1] 
		// maximum sum bitonic subarray 
		// 10
		task.maxSumBitonicSubArray(arr1, n);
		// Test B
		n = arr2.length;
		// [1 + 3 + 4 + 1] 
		// maximum sum bitonic subarray 
		// 9
		task.maxSumBitonicSubArray(arr2, n);
	}
}

Output

 Given sequence :   1  2  1  1  5  3  1  5  2  1
 Result : 10
 Given sequence :   1  3  4  1  3  2  1
 Result : 9
import Foundation;
/*
    Swift 4 Program for
    Maximum sum bitonic subarray using dynamic programming
*/
class BitonicSubarray
{
	// 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 maxSumBitonicSubArray(_ arr: [Int], _ n: Int)
	{
		if (n <= 0)
		{
			return;
		}
		// This is collects the sum of bitonic increasing 
		// subarry from left to right.
		var increasingSum: [Int] = Array(repeating: 0, count: n);
		// This is collects the sum of bitonic decreasing 
		// subarry from right to left.
		var decreasingSum: [Int] = Array(repeating: 0, count: n);
		// Assign first element value
		increasingSum[0] = arr[0];
		var i: Int = 1;
		// Calculate increasing sum from left to right
		while (i < n)
		{
			if (arr[i] > arr[i - 1])
			{
				increasingSum[i] = increasingSum[i - 1] + arr[i];
			}
			else
			{
				increasingSum[i] = arr[i];
			}
			i += 1;
		}
		// Assign last element value
		decreasingSum[n - 1] = arr[n - 1];
		i = n - 2;
		// Calculate decreasing sum from right to left
		while (i >= 0)
		{
			if (arr[i] > arr[i + 1])
			{
				decreasingSum[i] = decreasingSum[i + 1] + arr[i];
			}
			else
			{
				decreasingSum[i] = arr[i];
			}
			i -= 1;
		}
		// Initial value of result is minimum value.
		var result: Int = Int.min;
		i = 0;
		// Calcuate max sum bitonic subarray
		while (i < n)
		{
			result = self.maxValue(result, 
                     increasingSum[i] + decreasingSum[i] - arr[i]);
			i += 1;
		}
		print("\n Given sequence : ", terminator: "");
		self.display(arr, n);
		print("\n Result : ", result, terminator: "");
	}
}
func main()
{
	let task: BitonicSubarray = BitonicSubarray();
	// Array of positive integer elements
	let arr1: [Int] = [1, 2, 1, 1, 5, 3, 1, 5, 2, 1];
	let arr2: [Int] = [1, 3, 4, 1, 3, 2, 1];
	// Test A
	var n: Int = arr1.count;
	// [1 + 5 + 3 + 1] 
	// maximum sum bitonic subarray 
	// 10
	task.maxSumBitonicSubArray(arr1, n);
	// Test B
	n = arr2.count;
	// [1 + 3 + 4 + 1] 
	// maximum sum bitonic subarray 
	// 9
	task.maxSumBitonicSubArray(arr2, n);
}
main();

Output

 Given sequence :    1   2   1   1   5   3   1   5   2   1
 Result :  10
 Given sequence :    1   3   4   1   3   2   1
 Result :  9
/*
    Kotlin Program for
    Maximum sum bitonic subarray using dynamic programming
*/
class BitonicSubarray
{
	// 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 maxSumBitonicSubArray(arr: Array < Int > , n: Int): Unit
	{
		if (n <= 0)
		{
			return;
		}
		// This is collects the sum of bitonic increasing 
		// subarry from left to right.
		var increasingSum: Array < Int > = Array(n)
		{
			0
		};
		// This is collects the sum of bitonic decreasing 
		// subarry from right to left.
		var decreasingSum: Array < Int > = Array(n)
		{
			0
		};
		// Assign first element value
		increasingSum[0] = arr[0];
		var i: Int = 1;
		// Calculate increasing sum from left to right
		while (i < n)
		{
			if (arr[i] > arr[i - 1])
			{
				increasingSum[i] = increasingSum[i - 1] + arr[i];
			}
			else
			{
				increasingSum[i] = arr[i];
			}
			i += 1;
		}
		// Assign last element value
		decreasingSum[n - 1] = arr[n - 1];
		i = n - 2;
		// Calculate decreasing sum from right to left
		while (i >= 0)
		{
			if (arr[i] > arr[i + 1])
			{
				decreasingSum[i] = decreasingSum[i + 1] + arr[i];
			}
			else
			{
				decreasingSum[i] = arr[i];
			}
			i -= 1;
		}
		// Initial value of result is minimum value.
		var result: Int = Int.MIN_VALUE;
		i = 0;
		// Calcuate max sum bitonic subarray
		while (i < n)
		{
			result = this.maxValue(result, 
                     increasingSum[i] + decreasingSum[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: BitonicSubarray = BitonicSubarray();
	// Array of positive integer elements
	val arr1: Array < Int > = arrayOf(1, 2, 1, 1, 5, 3, 1, 5, 2, 1);
	val arr2: Array < Int > = arrayOf(1, 3, 4, 1, 3, 2, 1);
	// Test A
	var n: Int = arr1.count();
	// [1 + 5 + 3 + 1] 
	// maximum sum bitonic subarray 
	// 10
	task.maxSumBitonicSubArray(arr1, n);
	// Test B
	n = arr2.count();
	// [1 + 3 + 4 + 1] 
	// maximum sum bitonic subarray 
	// 9
	task.maxSumBitonicSubArray(arr2, n);
}

Output

 Given sequence :   1  2  1  1  5  3  1  5  2  1
 Result : 10
 Given sequence :   1  3  4  1  3  2  1
 Result : 9
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