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

import java.util.*;


public class Solution {
/**
     * 计算数组的最长递增子序列(Longest Increasing Subsequence, LIS)的长度
     *
     * @param arr 输入数组
     * @return 返回最长递增子序列的长度
     */
    public int LIS(int[] arr) {
        // 检查数组是否为空或长度为0
        if (arr == null || arr.length == 0) {
            return 0;
        }

        // 创建dp数组，dp[i]表示以arr[i]结尾的最长递增子序列的长度
        int[] dp = new int[arr.length];
        // 初始化dp数组，每个位置的初始值为1，因为每个元素本身就是一个长度为1的子序列
        Arrays.fill(dp, 1);
        // 用于记录最终结果
        int ans = 1;

        // 遍历数组，从第二个元素开始
        for (int i = 1; i < arr.length; i++) {
            // 对于每个元素，遍历它之前的所有元素
            for (int j = 0; j < i; j++) {
                // 如果当前元素arr[i]大于之前的某个元素arr[j]
                if (arr[i] > arr[j]) {
                    // 更新dp[i]的值，取当前dp[i]和dp[j]+1中的较大值
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }

            }
            // 更新最终结果，取当前最大值和dp[i]中的较大值
            ans = Math.max(ans, dp[i]);
        }
        // 返回最长递增子序列的长度
        return ans;
    }
}