# Maximum sum Bi-tonic sub-sequence in C++

## Introduction of Bi-tonic Subsequence:

A sequence of elements within an array that follows a particular pattern, which first increasing and then decreasing, is referred to as a bi-tonic subsequence in C++. Formally speaking, a subsequence arr[i1], arr[i2],..., arr[ik] of an array arr[] of size n is deemed bi-tonic if and only if:

• i1 < i2 < ... < ik (elements maintain their relative order in the array)
• arr[i1] <= arr[i2] <= ... <= arr[ik-1] >= arr[ik] (elements increase and then decrease)

## Problem Statement:

### Finding the Maximum Sum Bi-tonic Subsequence:

Finding the bi-tonic subsequence with the largest sum of its elements within a given array is the issue we are trying to solve. This issue has applications in several fields, such as:

• Analysis of the stock market (finding peak-and-dip patterns).
• Signal processing: identifying upward and downward trends.
• Optimization issues (determining the best schedules or distribution of resources).

## Problem Definition

Given: A n-integer array arr[].

• The task is to find the bi-tonic subsequence's maximum sum inside arr[].
• The maximum sum of a bi-tonic subsequence is the output.

Constraints:

• Positive and negative integers can be contained in the array arr[].
• There might or might not be a bi-tonic subsequence in the array.
• The output should be 0 (or any suitable value indicating no such subsequence) if there is no bi-tonic subsequence.

### Input and Output Requirements:

Input:

• An array arr[] of n integers represents the data to be analyzed.
• The number n represents the array's size.

Output:

The maximum sum of a bi-tonic subsequence within arr[] is represented by a single integer.

For instance:

• Input: arr[] = {1, 15, 51, 45, 33, 100, 12, 18, 9}, n = 9
• Output: 194 (corresponding to the bi-tonic subsequence 1, 15, 51, 100, 18, 9)

## Approach and Algorithm

Algorithm: Dynamic Programming

Steps:

Initialization:

• First create two arrays: MSIBS[n] and MDSB[n].
• The maximum sum of an increasing subsequence ending at the index i will be stored in MSIBS[i].
• Starting at the index i, MDSB[i] will hold the maximum sum of a decreasing subsequence.
• Set all other MSIBS and MDSB elements to 0 and MSIBS[0] to arr[0].

Calculate Increasing Subsequence Sums:

• Iterate from i = 1 to n-1:
• For each i, iterate from j = 0 to i-1:
• If arr[i] > arr[j] and MSIBS[i] < MSIBS[j] + arr[i]:
• Update MSIBS[i] with MSIBS[j] + arr[i].

Calculate Decreasing Subsequence Sums (in reverse order):

• Iterate from i = n-2 to 0:
• For each i, iterate from j = n-1 down to i+1:
• If arr[i] > arr[j] and MDSB[i] < MDSB[j] + arr[i]:
• Update MDSB[i] with MDSB[j] + arr[i].

Return maxSum.

Intuition:

• Finding the maximum increasing and decreasing subsequences is the problem's decomposition.
• For these subproblems, intermediate results are efficiently stored by MSIBS and MDSB.
• Building the bi-tonic subsequence by layering increasing and decreasing parts is possible.
• The right values from MSIBS and MDSB are combined to get the ultimate maximum sum.
• Due to avoiding redundant calculations, dynamic programming results in O(n^2) time complexity.

Implementation in C++

`#include <iostream>#include <vector>int maxSumBitonicSubsequence(const std::vector<int>& arr) {    int n = arr.size();    std::vector<int> MSIBS(n, 0);    std::vector<int> MSDSB(n, 0);    MSIBS[0] = arr[0];    for (int i = 1; i < n; i++) {        for (int j = 0; j < i; j++) {            if (arr[i] > arr[j] && MSIBS[i] < MSIBS[j] + arr[i]) {                MSIBS[i] = MSIBS[j] + arr[i];            }        }    }    MSDSB[n - 1] = arr[n - 1];    for (int i = n - 2; i >= 0; i--) {        for (int j = n - 1; j > i; j--) {            if (arr[i] > arr[j] && MSDSB[i] < MSDSB[j] + arr[i]) {                MSDSB[i] = MSDSB[j] + arr[i];            }        }    }    int maxSum = 0;    for (int i = 0; i < n; i++) {        int currentSum = MSIBS[i] + MSDSB[i] - arr[i];        maxSum = std::max(maxSum, currentSum);    }    return maxSum;}int main() {    std::vector<int> arr = {1, 15, 51, 45, 33, 100, 12, 18, 9};    int n = arr.size();    int maxSum = maxSumBitonicSubsequence(arr);    std::cout << "Maximum sum bi-tonic subsequence: " << maxSum << std::endl;    return 0;}`

Output:

### Time and Space Complexity

Time Complexity:

• O(n^2) due to the nested loops used to compute MDSB and MSIBS.
• There are n^2 operations because each loop iterates over n elements.

Space Complexity:

• O(n), mostly due to using two auxiliary arrays, each with size n: MSIBS and MDSB.
• Compared to n, additional space for variables and function calls is insignificant.

Enhancement for more expansive arrays:

• Consider different strategies such as divide-and-conquer or more sophisticated dynamic programming methods that could lower the time complexity to O(n log n) or even O(n).
• Space optimization: Investigate methods to reduce the space complexity to O(1) if space is a significant constraint. It may involve modifying the input array or employing a single auxiliary array.