Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample example
2.
Approach
2.1.
PseudoCode
3.
Implementation in C++
3.1.
Complexity Analysis
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

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

Author Urwashi Priya
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

In this blog, we will discuss a dynamic programming problem asked frequently in Interviews.
The problem is to find the Maximum sum subsequence of any size that is decreasing-increasing alternatively.

Problem Statement

We are given an array of n elements. We need to find a subsequence that satisfies the following two conditions:

  1. elements are first decreasing and then increasing in each step or vice versa
  2.  the sum of that subsequence is maximum.

And return the maximum sum.

Sample example

Array has 6 elements.
{1, 5, 7, 3, 4, 5}

The subsequence satisfying the above two conditions is 1,5,7,3,5.

Maximum Sum = 21 

Approach

The approach to Maximum sum subsequence of any size that is decreasing-increasing alternatively is given below. 
 

Define a function for backtracking which contains the three cases: a base case, alternating subsequence case and a case in which consecutive numbers are equal.

To find the maximum sum of alternating subsequences, define a separate function.

Declare two loops. The second loop will be dependent on the first loop.

Define an if condition to check for alternating subsequence. Then check if consecutive numbers are not equal. If numbers are equal, our current maximum sum remains the same. Else the new number will also be added.

Another condition checks if three adjacent elements are in the same order. If such a condition exists, perform backtracking.

Update the maximum sum and keep track of the state of elements.

Return maximum sum.
 

Since two loops are declared dependent on one another, our time complexity becomes O(n^2). An array of n elements is required to keep track of state and find alternating subsequence. So the space complexity becomes O(n).
Till now, I assume you must have got the basic conceptual idea of what has been asked and required in the given problem statement. So, I  recommend you first give it a try. try here

Please look at the algorithm to find the maximum sum subsequence of any size that is decreasing-increasing alternatively, and then again, you must give it a try.

PseudoCode

___________________________________________________________________

Procedure backtracking(int arr[], int maxSum[], int before[], int N, int root, int bef_root, int bbef_root):
___________________________________________________________________
1.  if (bbef_root == -1): return arr[bef_root]
2.  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]
3.  Else: return backtracking(arr, maxSum, before, N, root, bef_root, before[bbef_root])

end procedure


___________________________________________________________________

Procedure maxSumAlternatingSubsequence(int arr[], int N):
___________________________________________________________________
1.  maxSum[N], before[N]
2.  fill_n(&maxSum[0], N, 0)
3.  maxSum[0] = arr[0]
4.  before[0] = -1
5.  for (i = 1 to N):
		for (j = 0 to I):
			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]):
				currentMax = maxSum[j]
			else:
				currentMax = arr[i] + backtracking(arr, maxSum, before, N, i, j, before[before[j]])
			if (currentMax >= maxSum[i]):
				maxSum[i] = currentMax
				before[i] = j
6.  return *max_element(maxSum, maxSum + N);

end procedure
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

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;
}

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.

Previous article
Maximise Difference Between Sum Of Even And Odd-Indexed Elements Of A Subsequence
Next article
Maximum sum subsequence of any size which is decreasing-increasing alternatively
Live masterclass