最长上升子序列

最长上升子序列 (Longest Increasing Subsequence, LIS) 是一类典型的动态规划 (Dynamic Programming) 问题

对于一个序列 $b$ 来说，当 $b_1 < b_2 < \cdots < b_n$ 的时候，我们称这个序列为严格上升的序列。最长上升子序列，顾名思义，也就是在给定序列中最长的严格上升的子序列（不一定连续）

动态规划

考虑维护一个数组 dp[]，dp[i] 表示以第 $i$ 个数结尾的最长上升子序列的长度，对于长度为 $i$ 的序列 arr[] 来说，我们只要用 arr[i] 和序列 $i- 1$ 中的每一位进行比较，对于每一位小于 arr[i] 的数，都是有可能更新最长上升子序列长度的数，我们取其中最大一个，加上 arr[i] 本身（$dp[i] = max{dp[j]} + 1$），便是以第 $i$ 个数结尾的最长上升子序列的长度

所以我们可以得出状态转移方程
$$ dp[i] = max{dp[j]} + 1, j < i \ \&\&\ arr[j] < arr[i] $$

代码实现

for(int i = 0; i < nums.size(); ++i)
{
    dp[i] = 1;
    for(int j = 0; j < i; ++j)
    {
        if(arr[j] < arr[i])
            dp[i] = max(dp[i], dp[j] + 1);
    }
    ans = max(ans, dp[i]);
}

时间复杂度

显而易见，时间复杂度为 $O(n^2)$

二分 + 贪心

我们还是考虑维护一个数组 dp[] 及当前长度 $len$，dp[i] 表示目前计算的的上升子序列的第 $i$ 个元素的最小值

• 那么，每当我们拿到一个新元素 x ，我们和 dp[len] 进行对比，如果 dp[len] < x，那么就可以直接将 x 接入到最长上升子序列中，形成一个更长的子序列，并且 len++
• 如果 dp[len] >= x，找到 dp[] 中第一个大于等于 a 的元素，用 a 替换这个元素，这样能保证序列仍然是上升子序列，并且有更好的更新潜力（因为最后的元素变得更小了）

我们以序列 {1，4，5，3，4，5} 为例：

开始，我们将序列头 $1$ 添加进数组 dp[]

然后，我们将数组 dp[] 的末尾和 $4$ 进行判断，dp[] 数组末尾较小，dp[++len] = 4

同样，我们也将 $5$ 插入 dp[] 数组的尾部

当比较到 $3$ 时，我们发现，dp[] 数组的末尾 $> 3$，所以我们将 $3$ 插入到第一个大于它的位置，以期之后可以获得更小的末尾（这时序列的长度未变）

同样，因为末尾的 $5 > 4$，所以我们也将它插入到第一个大于它的位置

最后，我们将 $5$ 插入序列的末尾，得到了序列 {1，4，5，3，4，5}的最长上升子序列 {1，3，4，5}

代码实现

int len = 1;
dp[1] = 1;
for(int i = 2; i <= n; ++i)
{
    if(arr[i] > dp[len])
        dp[++len] = arr[i];
    else
        *upper_bound(dp + 1, dp + n, arr[i]) = arr[i];
}

时间复杂度

每次循环中最慢时间为 $\log n$，故总时间复杂度为 $O(n\log n)$

树状数组 $O(n\log n)$

// To Do