Find the maximum sum bitonic subsequence

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!