class Solution {
    public int lengthOfLIS(int[] nums) {
        int len =nums.length;
        if(len == 0)
            return 0;
        int[] record = new int[len];
        int max_index = len-1;
        for(int i = len-1; i >= 0 ; i-- ){
            if(nums[i]<nums[max_index]){
                record[i]= record[max_index]+1;
                max_index = i;
            }
            else{
                int j = i+1;
                while(j < len){
                    if(nums[j]>nums[i]){
                        record[i]= record[j]+1;
                        break;
                    }
                    j++;
                }
                if(j == len)
                    record[i] = 1;
                if(record[i] == record[max_index])
                    max_index = i;
            }
        }
        return record[max_index];
    }
}