本文最后更新于:4 个月前

代码

/**
 * @Classname LIS
 * @Description 最长递增子序列(LIS)
 * @Date 2020/5/9 下午 9:09
 * @Created by jerry
 */
public class LIS {
    public static int LIS(int[] nums) {
        if(nums.length <= 1){
            return nums.length;
        }
        //最大长度
        int max = 1;
        //dp[i]表示第i长的子序列,最后的元素
        int[] dp = new int[nums.length + 1];
        dp[1] = nums[0];
        for(int i = 1;i < nums.length;i++){
            //如果当前元素比最大的那个子串的最后一个元素还要大
            //那就直接长度加一,新子串的最后一个元素为当前元素
            if(nums[i] > dp[max]){
                dp[++max] = nums[i];
            }else if(nums[i] < dp[max]){
                //如果当前元素比最大的那个子串的最后一个元素要小
                //那就要更新dp数组,保证每一个子串都是最优解
                for(int j = 1 ;j <= max; j++){
                    //因为是递增,所以是<=,在将等于的时候直接终止循环
                    if(nums[i] <= dp[j]){
                        dp[j] = nums[i];
                        break;
                    }
                }
            }
        }
        for (int i = 1; i <= max; i++) {
            System.out.print(dp[i] + " ");
        }
        System.out.println();
        return max;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{10,9,2,5,3,7,101,18};
        System.out.println(LIS(nums));
    }
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!

[转]Java中邮件的发送 上一篇
【LeetCode】69. x 的平方根 下一篇

 目录