package NumToDelete;

public class NumToDelete {

   public int numToDelete(int[] elements){
      
      Solution sols[][] = new Solution[elements.length][2];
      
      //2 d array, in second d, [0] = optimal, [1] = cant delete the last element
      
      sols[0][0] = new Solution(elements[0],0);
      sols[0][1] = sols[0][0];
      
      int i = 0;
      for(i = 1; i < elements.length; i++){
         int cur = elements[i];
         Solution old[] = sols[i-1];
         if(cur >= old[0].maxElement){
            // we have an element > then all the elements
            // from the optimised list, hence both our lists contain this
            sols[i][0] = new Solution(cur, old[0].numToDel);
            sols[i][1] = sols[i][0];
         } else {
            //we have an element that is not the new max
            sols[i][0] = new Solution(old[0].maxElement, old[0].numToDel+1);
            sols[i][1] = sols[i][0];
            if(cur > elements[i-1]){
               //we have a solution that includes the last one that is ele[ -1]
               sols[i][1] = new Solution(cur, old[1].numToDel);
            }
            
            
            // this just ensures that the most optimal solution is in
            // the 0th position
            if(sols[i][1].numToDel < sols[i][0].numToDel){
               sols[i][0] = sols[i][1];
            }
         }
         
      }
      return sols[elements.length - 1][0].numToDel;
   }
   
   
   class Solution{
      public int maxElement;
      public int numToDel;
      
      Solution(int maxElement, int numToDel){
         this.maxElement = maxElement;
         this.numToDel = numToDel;
      }
   }
   
}