Java Solution - O(n^2)


#1

public class Solution {
// DO NOT MODIFY THE LIST. IT IS READ ONLY
public int lis(final List A) {
ArrayList lis=new ArrayList<>();

   for(int i=0;i<A.size();i++){
       lis.add(1);
   }
   
   for(int i=1;i<A.size();i++){
       for(int j=0;j<i;j++){
           if(A.get(i)>A.get(j)){
               lis.set(i,Math.max(lis.get(j)+1,lis.get(i)));
           }
           
       }
   }
   //System.out.println(lis);
   int max=0;
   for(int i=0;i<lis.size();i++){
       if(max<lis.get(i)){
           max=lis.get(i);
       }
   }
   return max;
    
}

}