Longest Increasing Subsequence

yangrd 发布于2019-08-16 10:27 / 1216人阅读

摘要：解题思路求不必连续的最长升序字符串长度，采用动态规划，利用状态表示以字符结尾的最长子串的长度，那么状态转移方程就是且必须小于另外还需维护一个最大长度。

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

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that 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?

解题思路

求不必连续的最长升序字符串长度，采用动态规划，利用状态dp[i]表示以字符nums[i]结尾的最长子串的长度，那么状态转移方程就是:
dp[i]=Math.max(dp[i],dp[j]+1);0<=j且nums[j]必须小于nums[i]
另外还需维护一个最大长度。

2.代码

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length==0) return 0;
        int[] dp=new int[nums.length];
        int maxLength=0;
        for(int i=0;i

海外云主机私有云 Increasing Subsequence Longest

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69821.html

[LintCode] Longest Increasing Subsequence

Problem Given a sequence of integers, find the longest increasing subsequence (LIS). You code should return the length of the LIS. Clarification Whats the definition of longest increasing subsequence?...

Flands 2019-08-14 14:22 评论0 收藏0
Longest Increasing Subsequence

摘要：题目链接主要两种方法和用，就是每次找出为结尾的最长的串的长度就好了。所以分解成就是，这个复杂度是。用一个数组，表示的长度为，表示长度为的，最右边的可能的最小值。这里只要求长度即可，那就直接用就可以了，整个用个数组就行了。 Longest Increasing Subsequence 题目链接：https://leetcode.com/problems... 主要两种方法：dp和gree...

FullStackDeveloper 2019-08-14 17:23 评论0 收藏0
[LeetCode] 300. Longest Increasing Subsequence

Problem 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...

luckyyulin 2019-08-19 11:13 评论0 收藏0
[leetcode]Longest Increasing Subsequence

摘要：对于一个递增子序列，想要增加它的长度，就必须在尾部添加一个更大的值。表示以结尾的最长递增序列的长度。长度增加的条件就是一个数字比大。长度最大值即为输入数组的长度。 Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given [10,...

wow_worktile 2019-08-14 16:52 评论0 收藏0
LeetCode[300] Longest Increasing Subsequence

摘要：再用二分法找当前值应该在排好序的数组中的插入位置。因为要找的是最长的序列，所以每次将排好序的数组中替换成已经排好序的，会能保证得到的结果是最长的。保证升序相等也要替换这个值 LeetCode[300] Longest Increasing Subsequence Given an unsorted array of integers, find the length of longe...

blankyao 2019-08-14 15:01 评论0 收藏0