题解 | #最长上升子序列(一)，dp#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] arr) {
        if(arr == null || arr.length == 0) return 0 ;
        //f[i]表示以arr[i]结尾的最长上升子序列长度
        int f[] = new int[arr.length] ;
        f[0] = 1 ;
        int max = Integer.MIN_VALUE ;
        for(int i = 1 ; i < arr.length ; i ++) {//计算每一个点
            f[i] = 1 ;
            for(int j = i - 1 ; j >= 0 ; --j) {//寻找比这个点小的点，并从寻找到的点传递过来
                if(arr[i] > arr[j]) {
                    f[i] = Math.max(f[i] , f[j] + 1) ;
                }
            }
            max = max < f[i] ? f[i] : max ;
        }
        return max ;
    }
}