## 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:

- elements are first decreasing and then increasing in each step or vice versa
- 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
```