P300 最长上升子序列

题目链接：300. 最长上升子序列.

题目描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例：

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

说明：

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
• 你算法的时间复杂度应该为 $O(n^2)$ 。

进阶： 你能将算法的时间复杂度降低到 $O(n\log n)$ 吗?

题解

方法一：动态规划

链接：动态规划.

思路

• ①将原问题分解为子问题

“求序列的前 $i$ 个元素的最长上升子序列的长度”是个子问题，但这样分解子问题，不具有“无后效性”的特点。

定义 $dp[i]=x$ 为前 $i$ 个元素（$nums[0]、nums[1]\dots nums[i-1]$）的最长上升子序列的长度为 $x$，但在这前 $i$ 个元素中，可能有多个上升子序列同时满足 $dp[i]=x$。有的子序列的最后一个元素比 $nums[i]$ 小，则加上$nums[i]$ 就能形成更长的上升子序列；有的序列最后一个元素不比 $nums[i]$ 小，不能加上 $nums[i]$ 形成更长的上升子序列。所以在当前的若干个状态值确定后，此后的过程演变不仅与这若干个状态的值有关，而且与之前经过哪条路径演变到当前这个状态有关，在本题中即：$dp[i+1]$ 不仅与 $dp[i]$ 有关，而且与在前 $i$ 个元素中选择哪条最长上升子序列的最后一个元素与 $nums[i]$ 进行比较有关。

子问题：“求以元素 $nums[i]$（$i=0、1、2...n-1$，$n$ 为数组 $nums$ 中元素个数）为终点的最长上升子序列的长度”。定义 $dp[i]$ 为以元素 $nums[i]$为终点的最长上升子序列的长度，共有 $n$ 个子问题，将这 $n$ 个子问题都解决了，那最大解就是原问题的解了，这就满足了问题具有最优子结构性质。

• ②确定状态

子问题只与一个变量有关：元素下标 $i$，所以每个子问题中最长上升子序列的终点元素的下标 $i$，就是状态，而状态 $i$ 对应的值就是以元素 $nums[i]$ 为终点的最长上升子序列的长度，所以我们只用一个一维数组就可以存储各个状态的值。共有 $n$ 个状态，它们构成状态空间。

• ③确定一些边界状态（初始状态）的值

显然，以元素 $nums[0]$ 为终点的最长上升子序列的长度为 $1$，所以有 $dp[0]=1$。

• ④确定状态转移方程

在计算 $dp[i]$ 时，我们假设已经将 $dp[0]、dp[1]、dp[i-1]$ 都已经计算出来了，那么要计算 $dp[i]$ 的值就要先在$dp[0]、dp[1]...dp[i-1]$ 中寻找 $dp[j]$（$0⩽j⩽i-1，j\in \mathbb{Z}$），$dp[j]$ 有：

d p [ j ] = max ⁡ ( d p [ k ] ， k ∈ s e t ) ， s e t = { k ∣ n u m s [ k ] < n u m s [ i ] ( 0 ⩽ k ⩽ i − 1 ， k ∈ Z ) } dp[j]=\max(dp[k]，k\in set)，set=\{k|nums[k]<nums[i](0\leqslant k\leqslant i-1，k\in \mathbb{Z})\} dp[j]=max(dp[k]，k∈set)，set={k∣nums[k]<nums[i](0⩽k⩽i−1，k∈Z)}

找到 $dp[j]$ 后，则有 $dp[i]=dp[j]+1$。

也就是 $dp[i]$ 的值为满足终点元素在 $nums[i]$ 的左边、终点元素小于 $nums[i]$ 的上升子序列中的最长上升子序列的长度加 1。

我们可以得到状态转移方程：
$$dp[i]=\{\begin{array}{ll}\max (dp[k]，k\in set)+1& set\ne \varnothing \\ 1& set=\varnothing \end{array}$$

s e t = { k ∣ n u m s [ k ] < n u m s [ i ] ( 0 ⩽ k ⩽ i − 1 ， k ∈ Z ) } set=\{k|nums[k]<nums[i](0\leqslant k\leqslant i-1，k\in \mathbb{Z})\} set={k∣nums[k]<nums[i](0⩽k⩽i−1，k∈Z)}

状态转移方程是递推形式的，所以在计算 $dp[i]$ 时，我们已经将 $dp[0]、dp[1]、dp[i-1]$ 都已经计算出来了。

• 原问题的解

最后，整个数组的最长上升子序列的长度 $maxLen$ 即数组 $dp$ 中的最大值。
$$maxLen=\max (dp[i])，(0⩽i⩽n-1，i\in \mathbb{Z})$$

算法

class Solution {
public:int lengthOfLIS(vector<int>& nums) {if(nums.size()==0){return 0;}int size=nums.size();vector<int> dp(size,1);int maxLen=dp[0];for(int i=1;i<size;++i){int temp=1;for(int j=0;j<i;++j){if(nums[i]>nums[j]){temp=dp[j]+1>temp?dp[j]+1:temp;}}dp[i]=temp;maxLen=dp[i]>maxLen?dp[i]:maxLen;}return maxLen;}
};

复杂度分析

假设数组中元素的个数为 $n$

• 时间复杂度：$O(n^2)$，因为动态规划中状态的数目为 $n$，在计算状态 $i$ 的值 $dp[i]$ 时需要遍历 $dp[0]、dp[1]...dp[i-1]$，时间复杂度为 $O(n)$，由动态规划解题的时间复杂度计算公式：
  $$时间复杂度=状态的数目\cdot 计算每个状态所需时间$$所以得到时间复杂度 $O(n^2)$ 。
• 空间复杂度：$O(n)$，需要一个长度为 $n$ 一维数组 $dp$ 来存储各个状态的值。

方法二：贪心 + 二分查找

思路

算法

复杂度分析