Maximum Sum Decreasing Subsequence (Dynamic Programming)

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...