An array, as we all know, is one of the most powerful and widely used data structures in computer languages. An array is a type of data structure that may hold comparable types of data. It is a very popular topic asked in coding interviews and one must practice questions on arrays to get a good grip on this topic. This blog will discuss the approach to solving the maximum sum subsequence of any size that is decreasing and increasing alternatively. Before jumping on the approach to the problem, let us first understand the problem.

Problem statement

Given an array, find the maximum sum subsequence whose elements are increasing and decreasing alternatively. Here, increasing and decreasing alternatively means that all the elements follow the same manner.

To understand it more clearly, let’s take an array [6, 4, 10, 9, 25, 16], as we can see that this array is decreasing and increasing in alternating order. As 4 is less than both 10 and 6 and 10 is greater than both 4 and 9, and so on. We have to find the maximum sum subsequence of this array.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Problem example

Input 1

Output 1

5

Explanation: The maximum sum subsequence that is increasing and decreasing alternatively is [1, 0, 1, 0, 3] and the resultant sum is 5.

Input 2

Output 2

18

Explanation: The maximum sum subsequence that is increasing and decreasing alternatively is [2, 5, 3, 8] and the resultant sum is 18.

Input 3

Output 3

26

Explanation: The maximum sum subsequence that is increasing and decreasing alternatively is [4, 8, 6, 8] and the resultant sum is 26.

Brute Force Approach

The brute force is simply finding all the subsequences recursively and checking the subsequence which follows the condition elements are increasing and decreasing alternatively and finding the maximum sum of it.

Algorithm

Every element has two options either we take in our subsequence or just leave it. For each index, we call two recursive functions one function includes that element, and the other will not include it.

The base case is if the current index is greater than the number of elements in the array then:

We check if elements are increasing and decreasing alternatively.

If it follows the above condition, we find the sum of the subsequence.

Update the answer with a maximum sum in the base case

Return the answer

Implementation

#include <bits/stdc++.h>
using namespace std;
int ans = 0;
int check(vector<int> &seq)
{
int n = seq.size();
// if size is 0 then return 0
if (n == 0)
return 0;
// if there is one element then return the first element
if (n == 1)
return seq[0];
bool cond1 = true; // when elements are a1<a2>a3<a4..
bool cond2 = true; // when elemnts are a1>a2<a3>a4...
int temp = 0;
int sum = seq[0];
for (int i = 1; i < n; i++)
{
// check for alternate condition where it will false
if (temp == 0 && seq[i - 1] >= seq[i])
cond1 = false;
if (temp == 1 && seq[i - 1] <= seq[i])
cond1 = false;
if (temp == 0 && seq[i - 1] <= seq[i])
cond2 = false;
if (temp == 1 && seq[i - 1] >= seq[i])
cond2 = false;
sum = sum + seq[i];
temp = 1 - temp;
}
// if any of condition is true then return sum
// otherwise 0
if (cond1 || cond2)
return sum;
else
return 0;
}
void recursive(vector<int> &a, int n, vector<int> &seq, int curr)
{
// base case
if (curr >= n)
{
int sum = check(seq);
ans = max(sum, ans);
return;
}
// transation
// include the current element
seq.push_back(a[curr]);
recursive(a, n, seq, curr + 1);
// not include the current element
seq.pop_back();
recursive(a, n, seq, curr + 1);
}
// driver code
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
vector<int> seq; // stores the subsequence
recursive(a, n, seq, 0);
cout << ans << endl;
}

Input

6
4 8 2 5 6 8

Output

26

Algorithm Complexity:

Time Complexity: O(N*2^N), where N is the size of the array. It is O(2^N) because for every element we have 2 options, so, for N element 2^n options and O(N) for checking condition in each case.

Space Complexity: O(N) as we are using a vector of at seq size; therefore, the overall space complexity will be O(N).

Efficient Approach

This approach considers using Dynamic programming along with backtracking. We need to store the maximum sum up to that particular element while traversing the array. Also, we need to store the value preceding the last element of each alternating subsequence with the maximum sum. In the iteration, we need to check the elements and the stored elements using an ‘IF’ condition as mentioned in the code. If the condition is true, add that element to the accumulated sum. Using this approach, we can find the maximum sum subsequence that is increasing and decreasing alternatively.

Algorithm

Create a function ‘getResult()’ that will accept two parameters, i.e., one array of integer ‘arr’, and the second one is the ‘N’ - the size of the vector ‘input’.

Create two arrays of integers ‘maxSum’ and ‘before’ to store the maximum sum of ‘N’ elements and to store the value preceding the previous element of each alternating subsequence with the maximum sum.

Make an iteration using a nested ‘for’ loop with the help of two variables ‘i’ and ‘j’, check for the ‘IF’ condition as stated in the code and if the condition is true, then update the value of variable ‘currentMax’ and if they are equal, then assign the value of the element at index ‘j’ of ‘maxSum’ to ‘currentMax’ and if not, then call the ‘helper’ function passing the parameter shown in the code and add the received value to ‘currentMax’ along with the value of the element at ‘ith’ index of ‘arr’.

In the ‘helper’ function, check for the base case, check for the conditions stated in the code, and return the value.

Return the max_element value of ‘maxSum’ and ‘maxSum + N.’

Implementation

// C++ code to find the maximum sum subsequence of an array that is increasing and decreasing alternately
#include <bits/stdc++.h>
using namespace std;
// Function for backtracking
int helper(int arr[], int maxSum[], int before[], int N, int root, int bef_root, int bbef_root)
{
// Base case:
if (bbef_root == -1)
{
int index = bef_root;
return arr[index];
}
// Subsequence with alternate parts
if ((arr[root] > arr[bef_root] && arr[bbef_root] > arr[bef_root]) || (arr[root] < arr[bef_root] && arr[bbef_root] < arr[bef_root]))
{
return arr[bef_root] + maxSum[bbef_root];
}
// Case when both are equal
else
{
return helper(arr, maxSum, before, N, root, bef_root, before[bbef_root]);
}
}
// Function to get result for the maximum sum subsequence
int getResult(int arr[], int N)
{
// Contains maximum sum according to the input vector
int maxSum[N];
// vector to store the index of preceeding element
int before[N];
fill_n(&maxSum[0], N, 0);
maxSum[0] = arr[0];
before[0] = -1;
// Traverse the array
for (int i = 1; i < N; i++)
{
for (int j = 0; j < i; j++)
{
int currentMax = 0;
if ((arr[i] > arr[j] && arr[before[j]] > arr[j]) || (arr[i] < arr[j] && arr[before[j]] < arr[j]) || before[j] == -1)
{
currentMax = (arr[i] == arr[j]) ? maxSum[j] : arr[i] + maxSum[j];
}
else if (arr[i] == arr[j])
{
// if both are equal then consider it only once
currentMax = maxSum[j];
}
else
{
// Backtracking if three elements follow the order
currentMax = arr[i] + helper(arr, maxSum, before, N, i, j, before[before[j]]);
}
if (currentMax >= maxSum[i])
{
maxSum[i] = currentMax;
before[i] = j;
}
}
}
// Get max result
return *max_element(maxSum, maxSum + N);
}
// Main function for finding the maximum sum subsequence that is increasing and decreasing alternatively
int main()
{
int n;
cin >> n;
int input[n];
for (int i = 0; i < n; i++)
cin >> input[i];
cout << getResult(input, n) << endl;
return 0;
}

Input

6
4 8 2 5 6 8

Output

26

Algorithm Complexity:

Time Complexity: O(N ^ 2) where N is the size of the array. It is O(N^2) because we have to traverse the array twice.

Space Complexity: O(N) as we are using a set of at max ‘N’ size, therefore, the overall space complexity will be O(N).

Frequently Asked Questions

What is the difference between fill_n() and fill() function?

The ‘fill_n’ function is used in this code to fill some default in the ‘maxSum’ array passed in it while the 'fill' function applies the value 'val' to all items in the range [begin, end], where 'begin' is the first position and 'end' is the last.

What is subsequence?

A subsequence is the subset of a sequence. The only thing to be kept in mind is that the order can’t be changed. For example some possible subsequence of {1,2,3,4} will be {1}, {2,4}, {1,2,4}, etc. It cant be {4,3} or {2.4,3}.

What is the difference between substring and subsequence?

Both are subsets of a sequence. In substring, consecutive elements are taken, whereas in subsequence, the order is maintained, some elements are deleted. For example, {1,2,4} can’t be substring of {1,2,3,4}. It is the subsequence of {1,2,3,4}.

Conclusion

In this article, we discussed the maximum sum subsequence of any size which is decreasing-increasing alternatively, we discussed the approach to solve this problem programmatically, the time and space complexities.