package commonProblems;import java.util.*;public class Microsort { /* * The recurrence for this numToDelete is... * MIN( * numToDelete(1 less element) + 1, * numToDelete's keep last element + add new element, * ) */ public int numToDelete(int[] elements){ int best = 0; int bestMax = elements[0]; int bestWithEnd = 0; //best max with end = the end obviously for(int i = 1; i < elements.length; i++){ if(elements[i] >= bestMax){ bestMax = elements[i]; bestWithEnd = best; } else { best++; //in the best case we would have to delete one more if (elements[i] < elements[i-1]){ //try to remove all items > cur, <= elements[i-1] int delCounter = 0; for(int j = i; j >= 0; j--){ if(elements[j]>elements[i] && elements[j] <= elements[i-1]){ delCounter++; } } // how many the last one had to delete + whatever has changed bestWithEnd = bestWithEnd + delCounter; } if(bestWithEnd < best){ best = bestWithEnd; bestMax = elements[i]; } } } return best; }}