1) Decrement with cost = 1
2) Delete an element completely from the array with cost = value of element
Any solution? convert here means you can get a different sequence, but it must be non decreasing.
A possible solution is with DP. C(n, m) = is the cost of getting n non decreasing elements with the constrain tha no element is greater than m. note that given the # cardinality of the set made up of the elements in #set(A), then 0 < m < #set(A)
C(1,m) = max(a - m, 0) // because at first step you can only decrease of value m C(n, m) = min ( // min: two options and want to find the min cost a[n] + C(n - 1, m), // delete operation at step n for value m // express the cost in function of step n-1 for value m
// and sum the cost of the specific delete op as specified
(a[n] <= m) ?C(n - 1, a[n]) // there is no need to decrement but for having// a non decreasing sequence we must have a value// non larger than a[n] for a[1..n-1]. That is// expressed inductively by C(n-1, a[n]): C(n-1, m) + // decrement with cost ma[n]- m // cost of decrementing a[n] to m with a[n] - m ops