Maximum sum subsequence of any size that is decreasing-increasing alternatively

Implementation in C++

// C++ code to find Maximum sum subsequence of any size that is decreasing-increasing alternatively
#include <bits/stdc++.h>
using namespace std;

// Function for backtracking
int backtracking(int arr[], int maxSum[], int before[], int N, int root, int bef_root, int bbef_root)
{
	// root, bef_root is used to keep track of state i and j
	// bbef_root => before[before[j]]

	// Base case:
	if (bbef_root == -1)
		return arr[bef_root];

	// alternating subsequence 
	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];
	}

	// if two numbers are consecutively equal
	else
	{
		return backtracking(arr, maxSum, before, N, root, bef_root, before[bbef_root]);
	}
}

int maxSumAlternatingSubsequence(int arr[], int N)
{
	int maxSum[N];
	int before[N];

	// initialising values in arrays:
	fill_n(&maxSum[0], N, 0);
	maxSum[0] = arr[0];
	before[0] = -1;

	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 arr[i] = arr[j] then considering only once
				currentMax = maxSum[j];
			}
			else
			{
			 	// If three adjacent elements are in same order, perform backtracking
				currentMax = arr[i] + backtracking(arr, maxSum, before, N, i, j, before[before[j]]);
			}

			if (currentMax >= maxSum[i])
			{
			 	// updating the maximum sum
				maxSum[i] = currentMax;
				before[i] = j;
			}
		}

	}
	// to get highest result in array
	return* max_element(maxSum, maxSum + N);
}

int main()
{
	int N;
	cin >> N;
	int arr[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	cout << maxSumAlternatingSubsequence(arr, N) << endl;
}

You can also try this code with Online C++ Compiler

Run Code

Input

6
1 5 7 3 4 5

Output

21

Complexity Analysis

Time Complexity: O(N^2).

Analysing Time Complexity:

Two loops are declared and the second loop is dependent on the first loop.

Space complexity: O(N). An array of n elements is required to keep track of the state and maximise the sum.

FAQs

1. What is subsequence?
   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}.
    
2. 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}.
    
3. What is fill_n? 
   It is a built-in function in c++. It is used to fill or occupy values till the nth position.

Key Takeaways

This article taught us how to find the Maximum sum subsequence of any size that is decreasing-increasing alternatively by approaching the problem using the backtracking concept. We discussed our problem's implementation using illustrations, pseudocode, and proper code.

We hope you could easily take away all critical and conceptual techniques like analysing problems by walking over the execution of the given examples and finding out the pattern followed.

Now, we strongly recommend you practice problem sets based on number theory to master your fundamentals and enhance your learning. You can get a wide range and variety of questions similar to this on Coding Ninjas Studio. 

It's not the end. You must also solve problems of similar type such as Minimum Subset Sum Difference.

Happy Coding.