leetcode-300-Longest Increasing Subsequence

amc 发布于2019-07-30 17:36 / 3231人阅读

摘要：本质找出最长的递增子序列的长度，可以是不连续的。应用判断满足一定条件的子序列的最大长度，用动态数组加以处理。二分法确定满足条件的位置。类似二分法查找元素，查找某种情况的子序列。

本质： 找出最长的递增子序列的长度，可以是不连续的。

  用一个数组存储 递增子序列，遍历原始数组，每增加一个数，往里添加到对应的顺序，记录他的位置，即为此数组的长度。
  成立的理由：每一个数添加以后，都有对应的子序列的长度，将它记录即可，然后最后取一个最长的。

思考：数组作为记录的作用，可以记录满足条件的数值，index可以作为索引，

  可以记录子数组，从中获取子数组的长度， 可以子数组修改子数组，加以覆盖，修改，根据最后一个值判断length。

应用： 判断满足一定条件的子序列的最大长度，用动态数组加以处理。

  二分法确定满足条件的位置。
  思路： 将满足条件的数值记录在数组，然后每次新数值插入此数组，记录下此时需要的信息。

类似： 二分法查找元素，查找某种情况的子序列。

class Solution:
    def lengthOfLIS(self, nums):
        length=len(nums)
        dp=[0]*length
        size=0
        for index,num in enumerate(nums):
            i,j=0,size
            while i!=j:
                m=(i+j)//2
                if dp[m]num:
                    j=m
                else:
                    i=m
                    break
            dp[i]=num
            size=max(size,i+1)
        return size
if __name__ == "__main__":
    nums = [10, 9, 2, 5, 3, 7,8,10,14,18,101,18,16,17,18]
    # nums=[3,1,4,1,5,9,2,6]
    print(len(nums))
    st = Solution()
    out=st.lengthOfLIS(nums)
    print(out)

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

转载请注明本文地址：https://www.ucloud.cn/yun/42303.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

摘要：题目要求找到整数数组中最长的递增子数组。该子数组可以为不连续的。如题目中例子所示，得到的最长子数组为。最后我们还需要遍历一遍全部子数组的长度并获得最大的长度。题目要求 Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given [...

eechen 2019-08-15 14:44 评论0 收藏0
[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