leetcode 300. Longest Increasing Subsequence

eechen 发布于2019-08-15 14:44 / 317人阅读

摘要：题目要求找到整数数组中最长的递增子数组。该子数组可以为不连续的。如题目中例子所示，得到的最长子数组为。最后我们还需要遍历一遍全部子数组的长度并获得最大的长度。

题目要求

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?

找到整数数组中最长的递增子数组。该子数组可以为不连续的。如题目中例子所示，[10, 9, 2, 5, 3, 7, 101, 18]得到的最长子数组为[2,3,7,101]。

思路一：动态规划

从动态规划的角度来说，假设要计算以第i位为结尾所构成的最长递增子数组，并且我们已经知道了第0位，第1位...第i-1位的任何一个值为最后一个数字时所能构成的最长子数组的长度。那么我们只需要从中找到值比当前小的值的下标，并且比较二者构成的子数组的长度，再从中获得最大长度的递增子数组，作为当前数组为最后一个值所构成的递增子数组的最大长度。

最后我们还需要遍历一遍全部子数组的长度并获得最大的长度。

   public int lengthOfLIS(int[] nums) {
        int length = nums.length;
        if(length==0) return 0;
        int T[] = new int[nums.length];
        for(int i = 1 ; i=0 ; j-- ){
                if(nums[j] < nums[i] && T[j] + 1 > T[i]){
                    T[i] = T[j] + 1;
                }
            }
        }
        int max = 0;
        for(int cur : T){
            max = Math.max(cur, max);
        }
        return max+1;
    }

思路二：大牛思路

这里附上一个解释的非常好的文章，我根据其思路的实现如下：

    public int lengthOfLIS2(int[] nums){
        int length = nums.length;
        if(length == 0) return 0;
        
        int[] tmp = new int[length];
        tmp[0] = nums[0];
        int max = 1;
        for(int i = 1 ; i=0 ; j--){
                if(j==0 && nums[i] < tmp[j]) tmp[j] = nums[i];
                else if(j == max-1 && nums[i] > tmp[j]){
                    tmp[j+1] = nums[i];
                    max++;
                    break;
                }
                else if(nums[i] < tmp[j] && nums[i] >tmp[j-1]){
                    tmp[j] = nums[i];
                    break;
                } 
            }
        }
        return max;
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

混合云 idc机房托管 Increasing Subsequence Longest Leetcod

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

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

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
[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-300-Longest Increasing Subsequence

摘要：本质找出最长的递增子序列的长度，可以是不连续的。应用判断满足一定条件的子序列的最大长度，用动态数组加以处理。二分法确定满足条件的位置。类似二分法查找元素，查找某种情况的子序列。本质：找出最长的递增子序列的长度，可以是不连续的。用一个数组存储递增子序列，遍历原始数组，每增加一个数，往里添加到对应的顺序，记录他的位置，即为此数组的长度。成立的理由：每一个数添加以后，都有对...

amc 2019-07-30 17:36 评论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
Longest Increasing Subsequence

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

FullStackDeveloper 2019-08-14 17:23 评论0 收藏0