当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.300.Longest Increasing Subsequence 最长上升子序列LIS

LeetCode.300.Longest Increasing Subsequence 最长上升子序列LIS

题目描述

300 Longest Increasing Subsequence
https://leetcode-cn.com/problems/longest-increasing-subsequence/

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:
There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?


解题过程

相似题目
LeetCode.1143.Longest Common Subsequence 最长公共子序列LCS
LeetCode.718.Maximum Length of Repeated Subarray 最长公共子串/最长重复子数组
LeetCode.300.Longest Increasing Subsequence 最长上升子序列LIS

动态规划

子序列是不需要连续的,我们知道了 nums[i] 之前所有比 nums[i] 小的子序列 0,…,j 的最长上升子序列长度,则再加1就是 0,…,i 的最长上升子序列长度。

设 lis[i] 是 nums[0…i] 的最长上升子序列的长度,则

$$ lis[i] = max(lis[j]) + 1, 0 \leq j \leq i-1 且 nums[j] < nums[i] $$

从前往后求出所有 lis[0…n-1] ,其中的最大值就是真个数组 nums 的 lis

时间复杂度 O(n^2),空间复杂度 O(n)

private static class SolutionV2020 {
    public int lengthOfLIS(int[] nums) {
        if (null == nums) {
            return 0;
        }
        if (nums.length < 2) {
            return nums.length;
        }
        // lis[i] 表示 0, ... i-1 中 最长上升子序列的长度
        int[] lis = new int[nums.length];
        // lis 的最大值
        int max = 0;
        // 找 nums[i] 之前比 nums[i] 小的数中的 lis 最大值
        for (int i = 1; i < nums.length; i++) {
            boolean update = false;
            int preLessMax = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] < nums[i]) {
                    update = true;
                    preLessMax = Math.max(preLessMax, lis[j]);
                }
            }
            if (update) {
                lis[i] = preLessMax + 1;
                max = Math.max(max, lis[i]);
            }
        }
        return max + 1;
    }
}

GitHub代码

algorithms/leetcode/leetcode/_300_LongestIncreasingSubsequence.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_300_LongestIncreasingSubsequence.java


上一篇 LeetCode.程序员面试金典.0106.CompressString 压缩字符串

下一篇 LeetCode.1071.Greatest Common Divisor of Strings 字符串的最大公因子

阅读
评论
430
阅读预计2分钟
创建日期 2020-03-14
修改日期 2020-03-14
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论