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;
   }
}