Minimum number of deletions to make a sorted sequence in java

Minimum number of deletions to make a sorted sequence in java

  December 20, 2017    

---

Idea is to find longest increasing subsequence and subtract it from n


Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class dmg
 {
     public static int LIS(int arr[],int n)
     {
         int dp[]=new int[n];
         Arrays.fill(dp,1);
         for(int i=0;i<n;++i)
         for(int j=0;j<i;++j)
         {
             if(arr[i]>arr[j])
             dp[i]=Math.max(dp[i],dp[j]+1);
         }
         int m=0;
         for(int x:dp)
         {
             m=Math.max(m,x);
         }
         return m;
     }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    System.out.println(n-LIS(arr,n));
}
}
}