Maximum Sum Decreasing Subsequence in C++

In this article, we are given an array arr[] of N integers. Our task is to find the Maximum Sum Decreasing Subsequence in C++.

A Maximum Sum Decreasing Subsequence (MSDS) is a subsequence of a given sequence of array. Here the sequence elements are ordered in decreasing arrangement and the sum of these elements is the highest.

Here, given a sequence of array a₁,a₂,?, a_n, the goal is to find a subsequence ai₁,ai₂,?,ai_k, where i₁>i₂>?>i₁, such that we say the subsequence is ai₁>ai₂>?>ai_k (ordered in a decreasing order). The sequence of terms ai₁+(ai₂)...+(ai_k) is shifted toward the higher values among all sequences that decrease and the lower terms always bind the higher term.

Let us dissect the definition −

• Subsequence: A subsequence is a sequence that can be derived from the source sequence by leaving all of its elements or eliminating some of them without changing their order.
• Decreasing Order: This is the order in which the numbers are placed in an MSDS and in that particular order each number is smaller than the previous one.
• Maximum Sum: The MSDS is the sequence with the highest possible sum. The number sequence is the sum of the decreasing elements in the subsequence.

Following is the input-output scenario to find the maximum sum of decreasing subsequence in C++ −

Input

arr[] = {3, 1, 6, 10, 5, 3, 2, 9, 1}

Output

21

Explanation

Decreasing subsequence with max sum is {10, 5, 3, 2, 1} = 10 + 5 + 3 + 2 + 1 = 21

Solution Approach

We will find the maximum sum of elements from the array such that the subsequence is strictly decreasing.

So, here we will use the dynamic programming approach to find the solution. Here, we will create a maxSum[] array which will store the maxSum till the index i. The follow formula is employed to find array values,

maxSum[i] = arr[i] + max(maxSum[0 … (*i-1)])

The maximum sum is given by the maximum element of the array maxSum[].

Example

Following is the program to illustrate the maximum sum decreasing subsequence in C++ −

#include <iostream>
using namespace std;
int findMaxSumDecSubSeq(int arr[], int N){
   int maximumSum = 0;
   int maxSum[N];
   for (int i = 0; i < N; i++)
      maxSum[i] = arr[i];
   for (int i = 1; i < N; i++)
      for (int j = 0; j < i; j++)
         if (arr[i] < arr[j] && maxSum[i] < maxSum[j] + arr[i])
         maxSum[i] = maxSum[j] + arr[i];
   for (int i = 0; i < N; i++)
         if (maximumSum < maxSum[i])
            maximumSum = maxSum[i];
   return maximumSum;
}
int main(){
   int arr[] = { 3, 1, 6, 10, 5, 3, 2, 9, 1 };
   int N= sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum sum of decreasing subsequence is "<<findMaxSumDecSubSeq(arr, N);
   return 0;
}

Output

The maximum sum of decreasing subsequence is 21