# Find the maximum sum bitonic subsequence

#### algorithm dynamic programming

The problem we are solving is that: Given a sequence of numbers in an array A[0.......N]. Find the sum of the maximum bitonic subsequence in the array.

This if approached using a naive algorithm will take exponential time O(N * (2^N)) but we can reduced it to O(N^2) using Dynamic programming. We will visit the idea of bitonic sequence, explore the naive approach and then, go into the dynamic programming technique to solve this efficiently.

## What is a Bitonic subsequence?

A subsequence in an array which first increases and then decreases.

Example:

A[]={5, 10, 16, 45, 32, 100, 10, 16, 9}

The bitoni subsequences are-:

• {5,10,16,32,16,9}
• {10,16,45,100,10,9}
• {16,32,100,10,9}

and so on.....

Maximum sum bitonic subsequence means the bitonic subsequence whose sum is maximum.

In the given example that bitonic subsequence is-:

{5,10,16,45,100,16,9}

And Sum=201.

For other subsequences, the sum of elements will be less than 201.

## Naive approach

The naive approach involves:

• Generating all subsequences (takes O(2^N) time complexity to generate all 2^N subsequences) (can be done using bitmap)
• For each subsequence:
• check if it is a bitonic sequence (taken O(N) time complexity)
• If it is a bitonic sequence, take the sum and check if it is large than the previously recorded sum

This way we can find the maximum sum bitonic subsequence in O(N * (2^N)) time complexity.

With Dynamic programming, we can reduce this to O(N^2) time complexity.

## Basic Idea of using Dynamic Programming

We are going to use Dynamic Programming approach to solve this problem.

We have to maintain two arrays namely:

• MSB[i] indicates the maximum sum of increasing bitonic subsequence ending at element A[i]
• MSD[i] indicates the sum of decreasing bitonic subsequence starting at A[i].

Once we have maintained these two arrays we find the **Maximum sum bitonic subsequence by finding maximum of MSB[i] + MSD[i] - Array[i] for all i.

Maximum sum bitonic subsequence = max(MSB[i]+MSD[i]-Arr[i])**.


## Pseudocode

Initialize MSB and MSD with the initial values:

for (int i = 0; i < n; i++)
{
MSB[i] = arr[i];
MSD[i] = arr[i];
}


Calculate MSB values:

// Compute MSB values from left to right
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{

if (arr[i] > arr[j] && MSB[i] < MSB[j] + arr[i])

MSB[i] = MSB[j] + arr[i];
}
}


Calculate MSD values:

// Compute MSD values from right to left
for (int i = n - 2; i >= 0; i--)
{
for (int j = n - 1; j > i; j--)
{
if (arr[i] > arr[j] && MSD[i] < MSD[j] + arr[i])
MSD[i] = MSD[j] + arr[i];
}
}


Calculate the final maximum value using MSB and MSD:

// Find the maximum value of MSB[i] + MSD[i] - arr[i]
for (int i = 0; i < n; i++)
{
max = max(max, (MSD[i] + MSB[i] - arr[i]));
}


## C++ Implementation

Following is the complete C++ implementation:

    #include <bits/stdc++.h>
using namespace std;

// Function return maximum sum of Bi-tonic sub-sequence
int MaxSum(int arr[], int n)
{
int max = INT_MIN;

// MSB[i]-: Maximum sum Increasing Bi-tonic
// subsequence ending with arr[i]
// MSD[i]-: Maximum sum Decreasing Bi-tonic
// subsequence starting with arr[i]
int MSB[n], MSD[n];
for (int i = 0; i < n; i++)
{
MSB[i] = arr[i];
MSD[i] = arr[i];
}

// Compute MSB values from left to right
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{

if (arr[i] > arr[j] && MSB[i] < MSB[j] + arr[i])

MSB[i] = MSB[j] + arr[i];
}
}

// Compute MSD values from right to left
for (int i = n - 2; i >= 0; i--)
{
for (int j = n - 1; j > i; j--)
{
if (arr[i] > arr[j] && MSD[i] < MSD[j] + arr[i])
MSD[i] = MSD[j] + arr[i];
}
}

// Find the maximum value of MSB[i] + MSD[i] - arr[i]
for (int i = 0; i < n; i++)
{
max = max(max, (MSD[i] + MSB[i] - arr[i]));
}

// return max sum of bi-tonic sub-sequence
return max;
}

int main()
{
int A[] = {5, 10, 16, 45, 32, 100, 10, 16, 9 };
int n = sizeof(A) / sizeof(A);
cout << "Maximum Sum Bitonic Subsequence : " << MaxSum(A, n);

return 0;
}


## Output-:

Maximum Sum Bitonic Subsequence : 201


## Time Complexity

The above approach uses Dynammic Programming and hence a nested loop so complexity is O(n^2) where n is the input size.

## Question

Find the longest increasing subsequence in a given array.

HAPPY CODING! #### Siddharth Agarwal

Intern at OpenGenus | Bachelor of Technology (2017 to 2021) in Computer Science at Institute of Engineering and Technology