【Leetcode】300—Longest|【Leetcode】300—Longest Increasing Subsequence 【Leetcode】300

一、题目描述给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例：

输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

二、代码实现方法：动态规划法 LISList[i]表示到第i位时最长上升序列的长度。显然LISList[0] = 1。对于任意的i不为零的情况，应该在i的左侧找一个下标 j ，其满足两个条件：

nums[ j ]比 nums[ i ] 小
它是所有满足条件1里 dp [j] 最大的那个
LISList[i] = max(LISList[j]) + 1

【【Leetcode】300—Longest|【Leetcode】300—Longest Increasing Subsequence】如果不存在这样的下标j，说明在0 ~ i - 1 的范围内，所有元素都比nums[i] 大，所以LISList[i] = 1，表示为nums[i] 自身成为一个长度为1 的上升子序列。

class Solution(object): def lengthOfLIS(self, nums): """ :type nums: List[int] :rtype: int """ if not nums: return 0 LISList = [1] * len(nums) for i in range(1, len(nums)): LIS = 0 for j in range(i): if nums[j] >= nums[i]: continue if LISList[j] > LIS: LIS = LISList[j] if LIS: LISList[i] = LIS + 1 return max(LISList)