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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] arr) {
        // write code here

        // 算法核心思想：动态规划

        // 处理特殊情况
        if (arr.length == 0) {
            return 0;
        }

        // dp[i] - 表示以i位置元素为结尾的最长严格上升子序列的长度
        // i - 从0（左）往n（右）推
        int[] dp = new int[arr.length];

        // 初始化dp
        // 当只有0位置元素时，上升子序列仅有其自己，故长度为1
        dp[0] = 1;

        // 递推dp
        int result = 1;
        for (int i = 1; i < arr.length; i++) {
            int max = 1;
            // 求解dp[i]，观察dp[0 ~ i-1]的所有位置，若有小于arr[i]的，就尝试让arr[i]接在其后面，+1
            for (int j = 0; j < i; j++) {
                // 先假设以arr[j]为结尾的最长严格上升子序列只有它自己
                int length = 1;
                if (arr[j] < arr[i]) {
                    // arr[i]可以接在以arr[j]为结尾的最长上升子序列后面
                    length = dp[j] + 1;
                }
                // 更新max
                if (length > max) {
                    max = length;
                }
            }
            // 根据max记录dp[i]
            dp[i] = max;
            // 更新最终的结果，及所有位置中最大的那个值
            if (dp[i] > result) {
                result = dp[i];
            }
        }
        return result;
    }
}