# Maximum Sum Decreasing Subsequence (Dynamic Programming)

Sign up for FREE 1 month of Kindle and read all our books for free.

Get FREE domain for 1st year and build your brand new site

Given an array of **n** positive integers, find the sum of the maximum sum decreasing subsequence (msds) of the given array such that the integers in the subsequence are sorted in decreasing order.

A subsequence of array is a sequence of elements from the original array which may or may not be continuous.

In other words, the task is to find a strictly decreasing subsequence with the maximum sum in the given array.

## Example

Input: {10, 12, 5, 7, 9, 1}

Output: 22

Explanation:

The decreasing subsequence with

the maximum sum is {12, 9, 1}

12 + 9 + 1 = 22

Try finding other decreasing subsequences and their sums manually to check your answer!

## Dynamic Programming (DP) Approach

- Let us assume
**arr[n]**as the input array and take an array**dp[n]**, where**dp[i] is the sum of the maximum sum decreasing subsequence till the element at arr[i]**. - Initialize
**dp[i]**to corresponding values in**arr[i]**(because the sum of the msds at any index**i**in**arr**would at least be**arr[i]**). - Loop through the array starting with index
**i = 1**(because the sum of msds till index**i = 0**would be**arr[0]**itself):- In each iteration, loop from index
**j = 0**to**j < i**to construct the**dp**array using the bottom up approach. - Now, if
**arr[i] < arr[j]**(strictly decreasing), then**dp[i] = maximum of (dp[i], dp[j] + arr[i])**.

- In each iteration, loop from index
- Finally, the largest element in the
**dp**array is the required answer.

In summary,

DP structure:

```
dp[i] = maximum sum decreasing subsequence till the element at arr[i]
```

Base case:

```
dp[0] = arr[0]
```

as there is only element in consideration for the first element at index 0.

Initialization:

```
for(int i = 0; i < n; i++)
{
dp[i] = arr[i];
}
```

Relation:

```
for(int i = 1; i < n; i++)
{
for(int j = 0; j < i; j++)
{
if(arr[i] < arr[j])
{
dp[i] = max(dp[i], dp[j] + arr[i]);
}
}
}
```

Answer

```
Answer = Maximum( dp[i] )
```

Let's understand the above approach with a simple example.

## Example

Input: {3, 2, 4}

Output: 6

Explanation:

Initialize dp array,

```
dp = {3, 2, 4}
```

i = 1

At j = 0,

```
Check arr[i] < arr[j] //true
max(dp[i], dp[j] + arr[i]) =
max(2, 3 + 2) = 5
```

dp = {3, 5, 4}

i = 2

At j = 0,

```
Check arr[i] < arr[j] //false
At j = 1,
Check arr[i] < arr[j] //false
```

Check the maximum value

in dp = {3, 5, 4}

5 is the answer

Take a bigger input array and try the above approach!

Now, let us take a look at the C++ solution for the problem.

## Implementation/ Solution

Following is the implementation of our Dynamic Programming approach in C++:

```
#include <bits/stdc++.h>
using namespace std;
int sumOfMsds(int arr[], int n)
{
int dp[n], maximum = 0;
// Initialize dp array
for(int i = 0; i < n; i++){
dp[i] = arr[i];
}
// Find maximum sum values
// using bottom up approach
for(int i = 1; i < n; i++){
for(int j = 0; j < i; j++){
if(arr[i] < arr[j]){
dp[i] = max(dp[i], dp[j] + arr[i]);
}
}
}
// Find the maximum of
// all the sum values
for(int i = 0; i < n; i++){
if(dp[i] > maximum){
maximum = dp[i];
}
}
return maximum;
}
int main()
{
int n; // size of array
cin >> n;
int arr[n];
for(int i = 0; i < n; i++)
cin >> arr[i];
cout << "Sum of maximum sum decreasing subsequence is "
<< sumOfMsds(arr, n);
return 0;
}
```

# Complexity

**Time Complexity: O(N ^{2})**

**Auxiliary Space Complexity: O(N)**

where N is the number of elements in the input.