Maximum Sum Decreasing Subsequence (Dynamic Programming)
Do not miss this exclusive book on Binary Tree Problems. Get it now for free.
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.
Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.