Longest Increasing Subsequence

Company: Amazon, Samsung, Paytm, BankBazaar.

Question: Given a sequence, find the length of the longest increasing subsequence from a given sequence .

The longest increasing subsequence means to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest
to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

Note: Duplicate numbers are not counted as increasing subsequence.

For example:
 length of LIS for 
{ 10, 22, 9, 33, 21, 50, 41, 60, 80 } is 6 and LIS is {10, 22, 33, 50, 60, 80}.

Input:

The first line contains an integer T, depicting total number of test cases. 
Then following T lines contains an integer N depicting the size of array and next line followed by the value of array.

Output:

Print the Max length of the subsequence in a separate line.

Constraints:

1 ≤ T ≤ 100
1 ≤ N ≤ 1000
0 ≤ A[i] ≤ 300

INPUT:

1

16

0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

OUTPUT:

6

CODE:

import java.util.*;

import java.lang.*;

import java.io.*;

class Solution {

public static void main (String[] args) {

Scanner sc = new Scanner (System.in);

int m = sc.nextInt();

for(int mi=0;mi<m;mi++){

   int n = sc.nextInt();

   int [] ar= new int [n];

   for(int i=0;i<n;i++){

       ar[i]=sc.nextInt();

   }

   System.out.println(lis(ar,n));

}

}

public static int lis(int []ar, int n){

   int lis[]=new int[n+1];

   int max=0;

   Arrays.fill(lis,1);

   for(int j=1;j<n;j++){

       for(int k=0;k<j;k++){

           if(ar[j]>ar[k] && lis[j]<lis[k]+1){

               lis[j]=lis[k]+1;

           }

       }

   }

   for(int loop=0;loop<n;loop++){

       if(max<lis[loop]){

           max=lis[loop];

       }

   }

   return max;

}

}

EXECUTION TIME: 0.16s