Longest Increasing Subsequence

The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50, 60, 80}.

More Examples:

Input  : arr[] = {3, 10, 2, 1, 20}
Output : Length of LIS = 3
The longest increasing subsequence is 3, 10, 20

Input  : arr[] = {3, 2}
Output : Length of LIS = 1
The longest increasing subsequences are {3} and {2}

Input : arr[] = {50, 3, 10, 7, 40, 80}
Output : Length of LIS = 4
The longest increasing subsequence is {3, 7, 40, 80}

Code:

import java.util.*;
import java.lang.*;
import java.io.*;

class LongestIncreasingSeq {
 public static void main (String[] args) {
  Scanner sc=new Scanner(System.in);
  int t=sc.nextInt();
  for(int y=0;y<t;y++)
  {
      int n=sc.nextInt();
      int arr[]=new int[n];
      int L[]=new int[n];
      for(int i=0;i<n;i++)
      {
          arr[i]=sc.nextInt();
      }
      L[0]=1;
      int max=0;
      for(int i=1;i<n;i++)
      {max=0;
          for(int j=0;j<i;j++)
          {
              if(arr[j]<arr[i])
              {
                        max=Math.max(max,L[j]);
              }
          }
          L[i]=Math.max((1+max),1);
      }
      int lis=0;
      for(int i=0;i<n;i++)
      {
         if(lis<L[i])
         {
             lis=L[i];
         }
      }
      System.out.println(lis); 
  }
 }
}

Time Complexity: O(n^2)

Space Complexity: O(n)