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]).
• 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²)
Auxiliary Space Complexity: O(N)

where N is the number of elements in the input.