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.