×

Search anything:

Maximum Sum Decreasing Subsequence (Dynamic Programming)

Internship at OpenGenus

FREE BOOK -> Problems for the day before your Coding Interview (on Amazon)

Price is set to 0. Click on Buy Now and it will be downloaded in your account.

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

where N is the number of elements in the input.

Maximum Sum Decreasing Subsequence (Dynamic Programming)
Share this