Problem:
You are given an array of positive integers. Convert it to a sorted array with minimum cost (minimum number of operations). Only valid operation are
1) Decrement -> cost = 1
2) Delete an element completely from the array -> cost = value of element
For example: 4,3,5,6, -> cost 1 //cost is 1 to make 4->3
10,3,11,12 -> cost // cost 3 to remove 3
Solution:
The first solution that came to mind for this problem is greedy solution. In each step we assume that array elements to the left of current elements are already sorted and we are adding current element to. The cost of delete(not adding current element) would be value of element itself and the cost of decrements would be sum of cost of reducing all elements to the left of current element that are more than current element.
However, this above approach does not work in all cases.
Consider 5 1 1 1 1 1 1 1 1 1, the above approach will remove all 1's and total cost will be 9 but the actual answer should be 4.
A DP solution is required to solve this problem.
Consider a function C, such that C(i,m) returns min cost required to make array A[0..i-1] sorted such that all elements in the array are less than m.
At any stage either the element should be deleted or decremented. For case where some elements need to be decremented.
m will be set of unique values in array A.
C(0,m) = max (a[0]-m,0), m unique values(A)
C(i,m) = Min (C(i-1,m) + a[i], a[i] <=m ? C(i-1,a[i]):C(i-1,m) + a[i] - m)
C(i-1,m) + a[i] is the scenario when current element is deleted, so the cost will be cost of making sorted array till i-1 with m as maximum value plus cost of deleting current element.
a[i] <=m ? C(i-1,a[i]):C(i-1,m) + a[i] - m is the scenario when current element is not deleted. If the current element is less than m then array elements to the left of it should not have any element more than a[i], so we find cost of making sorted array till i-1 with a[i] is maximum.
If the current element is more than m, then current element must be decremented. So the cost will be cost of making array till i-1 with m as maximum plus cost of reducing current element.
At the end we find Min(C(n-1,m)) for all m's.
Working Code
import java.util.Comparator;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
/**
* You are given an array of positive integers. Convert it to a sorted array
* with minimum cost (minimum number of operations). Only valid operation are <br>
* a. Decrement -> cost = 1 2)<br>
* b. Delete an element completely from the array -> cost = value of element For
* example: 4,3,5,6, -> cost 1 //cost is 1 to make 4->3 <br>
* 10,3,11,12 -> cost // cost 3 to remove 3
*
* Solution: The idea here is define a DP function c(i,m) such that it provides
* minimum cost required to make a[0..i] sorted such that no element is more
* than m. We start with c(0,m) and build our solution till c(n-1,m). The
* minimum value of c(n-1,m) is our solution.
*
* Here m is list of unique values in array A.
*
* @author sanahuja
*
*/
public class GetMinCostToMakeArraySorted {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int[] a = new int[n];
Map<Integer, Integer> c = new TreeMap<Integer, Integer>(new IntMaxSorter());
for (int i = 0; i < n; i++) {
a[i] = s.nextInt();
if (!c.containsKey(a[i])) {
c.put(a[i], 0);
}
}
// In first iteration, c(1,m) will be computed.
for (Integer m : c.keySet()) {
int cost = a[0] <= m ? 0 : a[0] - m;
c.put(m, cost);
}
for (int i = 1; i < n; i++) {
// Note value of M should be considered from high to low to avoid
// situation where c(i-1,a) (a<m) is actually returning c(i,m)
// because we are updating value iteratively. For this reason using tree map, but can be done more efficiently , tree map functionality may not be required.
for (Integer m : c.keySet()) {
int costDelete = c.get(m) + a[i];
int costDecrement = a[i] <= m ? c.get(a[i]) : c.get(m) + a[i]
- m;
int cost = costDecrement < costDelete ? costDecrement
: costDelete;
c.put(m, cost);
}
}
int minCost = Integer.MAX_VALUE;
for (Integer m : c.keySet()) {
if (c.get(m) < minCost) {
minCost = c.get(m);
}
}
System.out.println(minCost);
s.close();
}
}
class IntMaxSorter implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
}
