class Solution {
    public String longestPalindrome(String s) {
        char[] c = s.toCharArray();
        int str = s.length();
        boolean dp[][] = new boolean[str][str];
        // dp[i][j] = c[i]==c[j] && dp[i+1][j-1];
        int left = 0; // 左下标
        int right = 0; // 右下表
        int maxlen = 1; //长度  
        for(int i = 0;i < str;i++){
            dp[i][i] = true;
        }
        for(int len = 2;len <= str;len++){//枚举长度
            for(int i = 0;i < str;i++){//枚举起点
                int j = i+len-1; // j 是终点
                if(j >= str){
                    break;
                }
                if(c[i]==c[j] && (dp[i+1][j-1] || j-i ==1 )){
                    dp[i][j] = true;
                    if(j-i+1 > maxlen){
                        maxlen = j-i+1;
                        left = i;
                        right = j;
                    }
                }
            }
        }        
        return s.substring(left,right+1);
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0;
        int j = n-1;
        while(i < m && j >= 0){
            if(target == matrix[i][j]){
                return true;
            }else if(target > matrix[i][j]){
                i++;
            }else {
                j--;
            }
        }
        return false;
    }
}

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int dp[] = new int[len];
        int maxans = 0;
        for(int i = 0;i < len;i++){
            for(int j = 0;j < i;j++){
                if(nums[j]<nums[i]) dp[i] = Math.max(dp[i],dp[j]+1);
            }
            maxans =Math.max(dp[i],maxans);
        }
        return maxans+1;
    }
}