Get this book -> Problems on Array: For Interviews and Competitive Programming

Reading time: 30 minutes

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[0]);
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!