Given an array of N positive integers. The task is to 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.
Examples:
Input: arr[] = {5, 4, 100, 3, 2, 101, 1}
Output: 106
100 + 3 + 2 + 1 = 106Input: arr[] = {10, 5, 4, 3}
Output: 22
10 + 5 + 4 + 3 = 22
This problem is a variation of the Longest Decreasing Subsequence problem. The Optimal Substructure for the above problem will be:
Let arr[0..n-1] be the input array and MSDS[i] be the maximum sum of the MSDS ending at index i such that arr[i] is the last element of the MSDS.
Then, MSDS[i] can be written as:
MSDS[i] = a[i] + max( MSDS[j] ) where i > j > 0 and arr[j] > arr[i] or,
MSDS[i] = a[i], if no such j exists.
To find the MSDS for a given array, we need to return max(MSDS[i]) where n > i > 0.
Steps to solve the problem:
1. declare variables i,j and max=0.
2. declare an msds array of size n.
3. iterate through i=0 until n:
* assign arr[i] to msds[i].
4. iterate through i=1 until n:
* iterate through j=0 until n:
* check if arr[i] < arr[j]&&msds[i] < msds[j]+arr[i] than update msds[i] to sum of msds[j] and arr[i].
5. iterate through =0 until n:
* check if max is smaller than msds[i] than update max to msds[i].
6. return max.
Below is the implementation of the above approach:
C++
// CPP code to return the maximum sum// of decreasing subsequence in arr[]#include <bits/stdc++.h>using namespace std;// function to return the maximum// sum of decreasing subsequence// in arr[]int maxSumDS(int arr[], int n){ int i, j, max = 0; int MSDS[n]; // Initialize msds values // for all indexes for (i = 0; i < n; i++) MSDS[i] = arr[i]; // Compute maximum sum values // in bottom up manner for (i = 1; i < n; i++) for (j = 0; j < i; j++) if (arr[i] < arr[j] && MSDS[i] < MSDS[j] + arr[i]) MSDS[i] = MSDS[j] + arr[i]; // Pick maximum of all msds values for (i = 0; i < n; i++) if (max < MSDS[i]) max = MSDS[i]; return max;}// Driver Codeint main(){ int arr[] = { 5, 4, 100, 3, 2, 101, 1 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Sum of maximum sum decreasing subsequence is: " << maxSumDS(arr, n); return 0;} |
Java
// Java code to return the maximum sum// of decreasing subsequence in arr[]import java.io.*;import java.lang.*;class GfG { // function to return the maximum // sum of decreasing subsequence // in arr[] public static int maxSumDS(int arr[], int n) { int i, j, max = 0; int[] MSDS = new int[n]; // Initialize msds values // for all indexes for (i = 0; i < n; i++) MSDS[i] = arr[i]; // Compute maximum sum values // in bottom up manner for (i = 1; i < n; i++) for (j = 0; j < i; j++) if (arr[i] < arr[j] && MSDS[i] < MSDS[j] + arr[i]) MSDS[i] = MSDS[j] + arr[i]; // Pick maximum of all msds values for (i = 0; i < n; i++) if (max < MSDS[i]) max = MSDS[i]; return max; } // Driver Code public static void main(String argc[]) { int arr[] = { 5, 4, 100, 3, 2, 101, 1 }; int n = 7; System.out.println("Sum of maximum sum" + " decreasing subsequence is: " + maxSumDS(arr, n)); }}// This code os contributed by Sagar Shukla. |
Python3
# Python3 code to return the maximum sum# of decreasing subsequence in arr[]# Function to return the maximum# sum of decreasing subsequence# in arr[]def maxSumDS(arr, n): i, j, max = (0, 0, 0) MSDS=[0 for i in range(n)] # Initialize msds values # for all indexes for i in range(n): MSDS[i] = arr[i] # Compute maximum sum values # in bottom up manner for i in range(1, n): for j in range(i): if (arr[i] < arr[j] and MSDS[i] < MSDS[j] + arr[i]): MSDS[i] = MSDS[j] + arr[i] # Pick maximum of all msds values for i in range(n): if (max < MSDS[i]): max = MSDS[i] return max if __name__ == "__main__": arr=[5, 4, 100, 3, 2, 101, 1] n=len(arr) print("Sum of maximum sum decreasing subsequence is: ", maxSumDS(arr, n))# This code is contributed by Rutvik_56 |
C#
// C# code to return the// maximum sum of decreasing// subsequence in arr[]using System;class GFG{ // function to return the // maximum sum of decreasing // subsequence in arr[] public static int maxSumDS(int []arr, int n) { int i, j, max = 0; int[] MSDS = new int[n]; // Initialize msds values // for all indexes for (i = 0; i < n; i++) MSDS[i] = arr[i]; // Compute maximum sum values // in bottom up manner for (i = 1; i < n; i++) for (j = 0; j < i; j++) if (arr[i] < arr[j] && MSDS[i] < MSDS[j] + arr[i]) MSDS[i] = MSDS[j] + arr[i]; // Pick maximum of // all msds values for (i = 0; i < n; i++) if (max < MSDS[i]) max = MSDS[i]; return max; } // Driver Code static public void Main () { int []arr = {5, 4, 100, 3, 2, 101, 1}; int n = 7; Console.WriteLine("Sum of maximum sum" + " decreasing subsequence is: " + maxSumDS(arr, n)); }}// This code is contributed by m_kit |
PHP
<?php// PHP code to return the maximum sum// of decreasing subsequence in arr[]// function to return the maximum// sum of decreasing subsequence// in arr[]function maxSumDS($arr, $n){ $i; $j; $max = 0; $MSDS = array(); // Initialize msds values // for all indexes for ($i = 0; $i < $n; $i++) $MSDS[$i] = $arr[$i]; // Compute maximum sum values // in bottom up manner for ($i = 1; $i < $n; $i++) for ($j = 0; $j < $i; $j++) if ($arr[$i] < $arr[$j] && $MSDS[$i] < $MSDS[$j] + $arr[$i]) $MSDS[$i] = $MSDS[$j] + $arr[$i]; // Pick maximum of // all msds values for ($i = 0; $i < $n; $i++) if ($max < $MSDS[$i]) $max = $MSDS[$i]; return $max;}// Driver Code$arr = array (5, 4, 100, 3, 2, 101, 1 );$n = sizeof($arr);echo "Sum of maximum sum decreasing " . "subsequence is: ", maxSumDS($arr, $n);// This code is contributed by ajit?> |
Javascript
<script> // Javascript code to return the // maximum sum of decreasing // subsequence in arr[] // function to return the // maximum sum of decreasing // subsequence in arr[] function maxSumDS(arr, n) { let i, j, max = 0; let MSDS = new Array(n); // Initialize msds values // for all indexes for (i = 0; i < n; i++) MSDS[i] = arr[i]; // Compute maximum sum values // in bottom up manner for (i = 1; i < n; i++) for (j = 0; j < i; j++) if (arr[i] < arr[j] && MSDS[i] < MSDS[j] + arr[i]) MSDS[i] = MSDS[j] + arr[i]; // Pick maximum of // all msds values for (i = 0; i < n; i++) if (max < MSDS[i]) max = MSDS[i]; return max; } let arr = [5, 4, 100, 3, 2, 101, 1]; let n = 7; document.write("Sum of maximum sum" + " decreasing subsequence is: " + maxSumDS(arr, n));// This code is contributed by suresh07.</script> |
Sum of maximum sum decreasing subsequence is: 106
Complexity Analysis:
- Time complexity: O(N2)
- Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!