记录之前的最长上升子序列，转移到当前的元素时的状态变化

public static int LIS(int[] arr) {

    int len = arr.length;

    int[] dp = new int[len];// 记录数组每个下标元素开始的LIS长度

    // dp[0] = 1;所有位置都是1
    for (int i = 0; i < dp.length; i++) {// 初始化
        dp[i] = 1;
    }

    for (int i = 1; i < len; i++) {// 更新dp

        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {//比当前元素小的元素都可以和当前元素构成上升序列，找到之前求出的最大的一个上升长度
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }


    int res = 0;
    for (int i : dp) {//输出最大值，而不是末尾值
        res = Math.max(res, i);
    }
    return res;
}