# Maximum sum Bi-tonic Sub-sequence

Given an array of integers. A subsequence of arr[] is called Bitonic if it is first increasing, then decreasing.

Examples :

```Input : arr[] = {1, 15, 51, 45, 33,
100, 12, 18, 9}
Output : 194
Explanation : Bi-tonic Sub-sequence are :
{1, 51, 9} or {1, 50, 100, 18, 9} or
{1, 15, 51, 100, 18, 9}  or
{1, 15, 45, 100, 12, 9}  or
{1, 15, 45, 100, 18, 9} .. so on
Maximum sum Bi-tonic sub-sequence is 1 + 15 +
51 + 100 + 18 + 9 = 194

Input : arr[] = {80, 60, 30, 40, 20, 10}
Output : 210
```

This problem is a variation of standard Longest Increasing Subsequence (LIS) problem and longest Bitonic Sub-sequence.

We construct two arrays MSIBS[] and MSDBS[]. MSIBS[i] stores the sum of the Increasing subsequence ending with arr[i]. MSDBS[i] stores the sum of the Decreasing subsequence starting from arr[i]. Finally, we need to return the max sum of MSIBS[i] + MSDBS[i] – Arr[i].

Below is the implementation of above idea

## C/C++

 `// C++ program to find maximum sum of bi-tonic sub-sequence ` `#include ` `using` `namespace` `std; ` ` `  `// Function return maximum sum of Bi-tonic sub-sequence ` `int` `MaxSumBS(``int` `arr[], ``int` `n) ` `{ ` `    ``int` `max_sum = INT_MIN; ` ` `  `    ``// MSIBS[i] ==> Maximum sum Increasing Bi-tonic ` `    ``// subsequence ending with arr[i] ` `    ``// MSDBS[i] ==> Maximum sum Decreasing Bi-tonic ` `    ``// subsequence starting with arr[i] ` `    ``// Initialize MSDBS and MSIBS values as arr[i] for ` `    ``// all indexes ` `    ``int` `MSIBS[n], MSDBS[n]; ` `    ``for` `(``int` `i = 0; i < n; i++) { ` `        ``MSDBS[i] = arr[i]; ` `        ``MSIBS[i] = arr[i]; ` `    ``} ` ` `  `    ``// Compute MSIBS values from left to right */ ` `    ``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]; ` ` `  `    ``// Compute MSDBS 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] && MSDBS[i] < MSDBS[j] + arr[i]) ` `                ``MSDBS[i] = MSDBS[j] + arr[i]; ` ` `  `    ``// Find the maximum value of MSIBS[i] + MSDBS[i] - arr[i] ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``max_sum = max(max_sum, (MSDBS[i] + MSIBS[i] - arr[i])); ` ` `  `    ``// return max sum of bi-tonic sub-sequence ` `    ``return` `max_sum; ` `} ` ` `  `// Driver program ` `int` `main() ` `{ ` `    ``int` `arr[] = { 1, 15, 51, 45, 33, 100, 12, 18, 9 }; ` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr); ` `    ``cout << ``"Maximum Sum : "` `<< MaxSumBS(arr, n); ` ` `  `    ``return` `0; ` `} `

## Java

 `// java program to find maximum ` `// sum of bi-tonic sub-sequence ` `import` `java.io.*; ` ` `  `class` `GFG { ` ` `  `    ``// Function return maximum sum ` `    ``// of Bi-tonic sub-sequence ` `    ``static` `int` `MaxSumBS(``int` `arr[], ``int` `n) ` `    ``{ ` `        ``int` `max_sum = Integer.MIN_VALUE; ` ` `  `        ``// MSIBS[i] ==> Maximum sum Increasing Bi-tonic ` `        ``// subsequence ending with arr[i] ` `        ``// MSDBS[i] ==> Maximum sum Decreasing Bi-tonic ` `        ``// subsequence starting with arr[i] ` `        ``// Initialize MSDBS and MSIBS values as arr[i] for ` `        ``// all indexes ` `        ``int` `MSIBS[] = ``new` `int``[n]; ` `        ``int` `MSDBS[] = ``new` `int``[n]; ` `        ``for` `(``int` `i = ``0``; i < n; i++) { ` `            ``MSDBS[i] = arr[i]; ` `            ``MSIBS[i] = arr[i]; ` `        ``} ` ` `  `        ``// Compute MSIBS values from left to right */ ` `        ``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]; ` ` `  `        ``// Compute MSDBS 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] && MSDBS[i] < MSDBS[j] + arr[i]) ` `                    ``MSDBS[i] = MSDBS[j] + arr[i]; ` ` `  `        ``// Find the maximum value of MSIBS[i] + ` `        ``// MSDBS[i] - arr[i] ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `            ``max_sum = Math.max(max_sum, (MSDBS[i] + MSIBS[i] - arr[i])); ` ` `  `        ``// return max sum of bi-tonic ` `        ``// sub-sequence ` `        ``return` `max_sum; ` `    ``} ` ` `  `    ``// Driver program ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `arr[] = { ``1``, ``15``, ``51``, ``45``, ``33``, ``100``, ``12``, ``18``, ``9` `}; ` `        ``int` `n = arr.length; ` `        ``System.out.println(``"Maximum Sum : "` `+ MaxSumBS(arr, n)); ` `    ``} ` `} ` ` `  `// This code is contributed by vt_m `

## Python

 `# Dynamic Programming implementation of maximum sum of bitonic subsequence  ` ` `  `# Function return maximum sum of Bi-tonic sub-sequence ` `def` `max_sum(arr, n): ` ` `  `    ``# MSIBS[i] ==> Maximum sum Increasing Bi-tonic ` `    ``# subsequence ending with arr[i] ` `    ``# MSDBS[i] ==> Maximum sum Decreasing Bi-tonic ` `    ``# subsequence starting with arr[i] ` ` `  `    ``# allocate memory for MSIBS and initialize it to arr[i] for ` `    ``# all indexes ` `    ``MSIBS ``=` `arr[:] ` ` `  `    ``# Compute MSIBS values from left to right ` `    ``for` `i ``in` `range``(n): ` ` `  `        ``for` `j ``in` `range``(``0``, i): ` ` `  `            ``if` `arr[i] > arr[j] ``and` `MSIBS[i] < MSIBS[j] ``+` `arr[i]: ` ` `  `                ``MSIBS[i] ``=` `MSIBS[j] ``+` `arr[i] ` ` `  `    ``# allocate memory for MSDBS and initialize it to arr[i] for ` `    ``# all indexes ` `    ``MSDBS ``=` `arr[:] ` ` `  `    ``# Compute MSDBS values from right to left ` `    ``for` `i ``in` `range``(``1``, n ``+` `1``): ` ` `  `        ``for` `j ``in` `range``(``1``, i): ` ` `  `            ``if` `arr[``-``i] > arr[``-``j] ``and` `MSDBS[``-``i] < MSDBS[``-``j] ``+` `arr[``-``i]: ` `     `  `                ``MSDBS[``-``i] ``=` `MSDBS[``-``j] ``+` `arr[``-``i] ` ` `  `    ``max_sum ``=` `float``(``"-Inf"``)  ` ` `  `    ``# Find the maximum value of MSIBS[i] + MSDBS[i] - arr[i] ` `    ``for` `i, j, k ``in` `zip``(MSIBS, MSDBS, arr): ` ` `  `        ``max_sum ``=` `max``(max_sum, i ``+` `j ``-` `k) ` ` `  `    ``# return max sum of bi-tonic sub-sequence ` `    ``return` `max_sum ` ` `  ` `  `# Driver program to test the above function ` `def` `main(): ` ` `  `    ``arr ``=` `[``1``, ``15``, ``51``, ``45``, ``33``, ``100``, ``12``, ``18``, ``9``] ` ` `  `    ``n ``=` `len``(arr) ` ` `  `    ``print` `max_sum(arr, n) ` ` `  `if` `__name__ ``=``=` `'__main__'``: ` `    ``main() ` `# This code is contributed by Neelam Yadav `

## C#

 `// C# program to find maximum ` `// sun of bi-tonic sub-sequence ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// Function return maximum sum ` `    ``// of Bi-tonic sub-sequence ` `    ``static` `int` `MaxSumBS(``int``[] arr, ``int` `n) ` `    ``{ ` `        ``int` `max_sum = ``int``.MinValue; ` ` `  `        ``// MSIBS[i] ==> Maximum sum Increasing Bi-tonic ` `        ``// subsequence ending with arr[i] ` `        ``// MSDBS[i] ==> Maximum sum Decreasing Bi-tonic ` `        ``// subsequence starting with arr[i] ` `        ``// Initialize MSDBS and MSIBS values as arr[i] for ` `        ``// all indexes ` `        ``int``[] MSIBS = ``new` `int``[n]; ` `        ``int``[] MSDBS = ``new` `int``[n]; ` `        ``for` `(``int` `i = 0; i < n; i++) { ` `            ``MSDBS[i] = arr[i]; ` `            ``MSIBS[i] = arr[i]; ` `        ``} ` ` `  `        ``// Compute MSIBS values from left to right */ ` `        ``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]; ` ` `  `        ``// Compute MSDBS 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] && MSDBS[i] < MSDBS[j] + arr[i]) ` `                    ``MSDBS[i] = MSDBS[j] + arr[i]; ` ` `  `        ``// Find the maximum value of MSIBS[i] + ` `        ``// MSDBS[i] - arr[i] ` `        ``for` `(``int` `i = 0; i < n; i++) ` `            ``max_sum = Math.Max(max_sum, (MSDBS[i] + MSIBS[i] - arr[i])); ` ` `  `        ``// return max sum of bi-tonic ` `        ``// sub-sequence ` `        ``return` `max_sum; ` `    ``} ` ` `  `    ``// Driver program ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int``[] arr = { 1, 15, 51, 45, 33, 100, 12, 18, 9 }; ` `        ``int` `n = arr.Length; ` `        ``Console.WriteLine(``"Maximum Sum : "` `+ MaxSumBS(arr, n)); ` `    ``} ` `} ` ` `  `// This code is contributed by vt_m `

## PHP

 ` Maximum sum Increasing  ` `    ``// Bi-tonic subsequence ending with arr[i] ` `    ``// MSDBS[i] ==> Maximum sum Decreasing  ` `    ``// Bi-tonic subsequence starting with arr[i] ` `    ``// Initialize MSDBS and MSIBS values ` `    ``// as arr[i] for all indexes ` `    ``\$MSIBS` `= ``array``(); ` `    ``\$MSDBS` `= ``array``(); ` `    ``for` `(``\$i` `= 0; ``\$i` `< ``\$n``; ``\$i``++)  ` `    ``{ ` `        ``\$MSDBS``[``\$i``] = ``\$arr``[``\$i``]; ` `        ``\$MSIBS``[``\$i``] = ``\$arr``[``\$i``]; ` `    ``} ` ` `  `    ``// Compute MSIBS values ` `    ``// from left to right */ ` `    ``for` `(``\$i` `= 1; ``\$i` `< ``\$n``; ``\$i``++) ` `        ``for` `(``\$j` `= 0; ``\$j` `< ``\$i``; ``\$j``++) ` `            ``if` `(``\$arr``[``\$i``] > ``\$arr``[``\$j``] &&  ` `                ``\$MSIBS``[``\$i``] < ``\$MSIBS``[``\$j``] +  ` `                             ``\$arr``[``\$i``]) ` `                ``\$MSIBS``[``\$i``] = ``\$MSIBS``[``\$j``] +  ` `                             ``\$arr``[``\$i``]; ` ` `  `    ``// Compute MSDBS values  ` `    ``// from right to left ` `    ``for` `(``\$i` `= ``\$n` `- 2; ``\$i` `>= 0; ``\$i``--) ` `        ``for` `(``\$j` `= ``\$n` `- 1; ``\$j` `> ``\$i``; ``\$j``--) ` `            ``if` `(``\$arr``[``\$i``] > ``\$arr``[``\$j``] &&  ` `                ``\$MSDBS``[``\$i``] < ``\$MSDBS``[``\$j``] +  ` `                             ``\$arr``[``\$i``]) ` `                ``\$MSDBS``[``\$i``] = ``\$MSDBS``[``\$j``] +  ` `                             ``\$arr``[``\$i``]; ` ` `  `    ``// Find the maximum value of ` `    ``// MSIBS[i] + MSDBS[i] - arr[i] ` `    ``for` `(``\$i` `= 0; ``\$i` `< ``\$n``; ``\$i``++) ` `        ``\$max_sum` `= max(``\$max_sum``, (``\$MSDBS``[``\$i``] +  ` `                                  ``\$MSIBS``[``\$i``] -  ` `                                  ``\$arr``[``\$i``])); ` ` `  `    ``// return max sum of  ` `    ``// bi-tonic sub-sequence ` `    ``return` `\$max_sum``; ` `} ` ` `  `// Driver Code ` `\$arr` `= ``array``(1, 15, 51, 45, 33,  ` `             ``100, 12, 18, 9); ` `\$n` `= ``count``(``\$arr``); ` `echo` `"Maximum Sum : "` `,  ` `      ``MaxSumBS(``\$arr``, ``\$n``); ` ` `  `// This code is contributed ` `// by shiv_bhakt. ` `?> `

Output:

```Maximum Sum : 194
```

Time complexity : O(n2)