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 : 9package 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 : 9import 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 : 9import 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
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