Posted on by Kalkicode
Code Dynamic Programming

# Maximum sum bitonic subarray using dynamic programming

Dynamic programming is a powerful technique used to solve a variety of optimization problems. One such problem is finding the maximum sum bitonic subarray in an array. A bitonic subarray is a subarray in which the elements are first increasing and then decreasing.

## Problem Statement

Given an array of positive integers, we need to find the maximum sum of a bitonic subarray.

## Pseudocode Algorithm

``````
// Function to calculate the maximum sum bitonic subarray
maxSumBitonicSubArray(arr, n)
if n <= 0
return
initialize increasingSum[n]
initialize decreasingSum[n]
increasingSum[0] = arr[0]
for i = 1 to n-1
if arr[i] > arr[i - 1]
increasingSum[i] = increasingSum[i - 1] + arr[i]
else
increasingSum[i] = arr[i]
decreasingSum[n - 1] = arr[n - 1]
for i = n - 2 to 0
if arr[i] > arr[i + 1]
decreasingSum[i] = decreasingSum[i + 1] + arr[i]
else
decreasingSum[i] = arr[i]
result = INT_MIN
for i = 0 to n-1
result = max(result, increasingSum[i] + decreasingSum[i] - arr[i])
display(arr, n)
display(result)
```
```

The above algorithm is implemented using dynamic programming. It consists of three main steps:

1. Calculate the sum of the increasing bitonic subarray from left to right and store it in the array `increasingSum`.
2. Calculate the sum of the decreasing bitonic subarray from right to left and store it in the array `decreasingSum`.
3. Find the maximum sum by iterating through the array and adding the corresponding values from `increasingSum` and `decreasingSum`.

## Code Solution

``````// 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)
{
// 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
// Test B
n = arr2.length;
// [1 + 3 + 4 + 1]
// maximum sum bitonic subarray
// 9
}
}``````

#### 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()
{
// 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
// Test B
n = sizeof(arr2) / sizeof(arr2[0]);
// [1 + 3 + 4 + 1]
// maximum sum bitonic subarray
// 9
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)
{
// 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
// Test B
n = arr2.Length;
// [1 + 3 + 4 + 1]
// maximum sum bitonic subarray
// 9
}
}``````

#### 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()
{
// 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
// Test B
\$n = count(\$arr2);
// [1 + 3 + 4 + 1]
// maximum sum bitonic subarray
// 9
}
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()
{
// 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
// Test B
n = arr2.length;
// [1 + 3 + 4 + 1]
// maximum sum bitonic subarray
// 9
}
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() :
#  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
#  Test B
n = len(arr2)
#  [1 + 3 + 4 + 1]
#  maximum sum bitonic sublist
#  9

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()
#  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
#  Test B
n = arr2.length
#  [1 + 3 + 4 + 1]
#  maximum sum bitonic subarray
#  9
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
// Test B
n = arr2.length;
// [1 + 3 + 4 + 1]
// maximum sum bitonic subarray
// 9
}
}``````

#### 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()
{
// 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
// Test B
n = arr2.count;
// [1 + 3 + 4 + 1]
// maximum sum bitonic subarray
// 9
}
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
{
// 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
// Test B
n = arr2.count();
// [1 + 3 + 4 + 1]
// maximum sum bitonic subarray
// 9
}``````

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

## Resultant Output Explanation

Let's consider two test cases to understand the output:

### Test Case A:

``````
int arr1[] = {1, 2, 1, 1, 5, 3, 1, 5, 2, 1};
int n = sizeof(arr1) / sizeof(arr1[0]);
maxSumBitonicSubArray(arr1, n);
```
```

The given sequence is: 1 2 1 1 5 3 1 5 2 1

The maximum sum bitonic subarray in this sequence is 1 + 5 + 3 + 1, which equals 10.

The result displayed is: 10

### Test Case B:

``````
int arr2[] = {1, 3, 4, 1, 3, 2, 1};
int n = sizeof(arr2) / sizeof(arr2[0]);
maxSumBitonicSubArray(arr2, n);
```
```

The given sequence is: 1 3 4 1 3 2 1

The maximum sum bitonic subarray in this sequence is 1 + 3 + 4 + 1, which equals 9.

The result displayed is: 9

## Time Complexity

The time complexity of this algorithm is O(n), where n is the size of the input array. This is because we iterate through the array only once to calculate the increasing and decreasing sums, and then iterate again to find the maximum sum bitonic subarray.

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

Categories
Relative Post