思路一动态规划建立dp表dp[i]表示含第i个数字的最长上升子序列的长度求dp[i]时向前遍历找出比i元素小的元素j则动态方程为dp[i] max(dp[i],dp[j] 1)class Solution(object): def lengthOfLIS(self, nums): size len(nums) if size 1: return size dp [1] * size for i in range(1, size): for j in range(i): if nums[i] nums[j]: # 1 的位置不要加错了 dp[i] max(dp[i], dp[j] 1) # 最后要全部走一遍看最大值 return max(dp)思路二二分查找利用一个cell数组用于保存最长上升子序列对原序列进行遍历将每位元素二分插入cell中如果cell中的元素都比它小直接将它插到最后否则利用二分查找用它覆盖掉比他大的元素中最小的那个总之思想就是让 cell 中存储比较小的元素。这样cell 未必是真实的最长上升子序列但长度是对的。class Solution(object): def lengthOfLIS(self, nums): size len(nums) if size 1: return size cell [nums[0]] for i in nums[1:]: #cell中元素都比它小 if i cell[-1]: cell.append(i) continue #否则利用二分查找进行覆盖 l, r 0, len(cell) - 1 while l r: m l (r - l) // 2 if cell[m] i: l m 1 else: r m cell[l] i return len(cell)
思路一动态规划建立dp表dp[i]表示含第i个数字的最长上升子序列的长度求dp[i]时向前遍历找出比i元素小的元素j则动态方程为dp[i] max(dp[i],dp[j] 1)class Solution(object): def lengthOfLIS(self, nums): size len(nums) if size 1: return size dp [1] * size for i in range(1, size): for j in range(i): if nums[i] nums[j]: # 1 的位置不要加错了 dp[i] max(dp[i], dp[j] 1) # 最后要全部走一遍看最大值 return max(dp)思路二二分查找利用一个cell数组用于保存最长上升子序列对原序列进行遍历将每位元素二分插入cell中如果cell中的元素都比它小直接将它插到最后否则利用二分查找用它覆盖掉比他大的元素中最小的那个总之思想就是让 cell 中存储比较小的元素。这样cell 未必是真实的最长上升子序列但长度是对的。class Solution(object): def lengthOfLIS(self, nums): size len(nums) if size 1: return size cell [nums[0]] for i in nums[1:]: #cell中元素都比它小 if i cell[-1]: cell.append(i) continue #否则利用二分查找进行覆盖 l, r 0, len(cell) - 1 while l r: m l (r - l) // 2 if cell[m] i: l m 1 else: r m cell[l] i return len(cell)
