企业官网建设流程全解析

思路一：动态规划

建立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)