×

Search anything:

# Maximum Sum Decreasing Subsequence (Dynamic Programming)

#### Algorithms Dynamic Programming (DP) FREE BOOK -> Problems for the day before your Coding Interview (on Amazon)

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 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]).
• 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 = arr
``````

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

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(N2)
Auxiliary Space Complexity: O(N)

where N is the number of elements in the input.