1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

        public int LIS(int[] arr) {
        if(arr==null||arr.length==0){
            return 0;
        }

        int[] dp = new int[arr.length];
        Arrays.fill(dp, 1);
        int ans = 1;

        for(int i=1;i<arr.length;i++){
            for(int j=0;j<i;j++){
                if(arr[i]>arr[j]){
                    dp[i]=Math.max(dp[j]+1, dp[i]);
                }
                
            }
            ans = Math.max(ans,dp[i]);
        }
        return ans;
    }