最长上升子序列(Longest Increasing Subsequence)

题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$，请求出它的最长上升子序列的长度，以及有多少个位置上的元素可能出现在最长上升子序列中，多少个位置上的元素一定出现在最长上升子序列中？

例如，给定序列 3,1,2,5,4中： {1,2,5}与{1,2,4}均为满足条件的最长上升子序列，该序列的最长上升子序列的长度为 $3$。元素1,2,4,5 均有可能出现在最长上升子序列中，故有 $4$ 个位置上的元素可能出现在最长上升子序列中，而元素 1,2 必然出现在最长上升子序列中，故有 $2$ 个位置上的元素一定出现在最长上升子序列中。

输入格式

输入共两行：

输入第一行，一个整数 $n$，表示给定序列元素个数

输入第二行，$n$ 个正整数，分别表示 $a_1,a_2,\ldots,a_n$。

输出格式

输出共一行：第一行：输出三个数字，分别表示最长上升子序列长度，可能出现在最长上升子序列中的元素位置个数，及必然出现在最长上升子序列中元素位置个数，用空格隔开。

数据范围

• 对于 30% 的数据，$1\leq n \leq 10$；
• 对于 70% 的数据，$1\leq n \leq 10^4$；
• 对于 100% 的数据，$1\leq n \leq 10^5$；$1 \leq a_i \leq 10^9$

样例输入 #1

5
3 1 2 5 4

样例输出 #1

3 4 2

样例说明 #1

样例说明请见题面

样例输入 #2

6
4 5 6 1 2 3

样例输出 #2

3 6 0

样例说明 #2

最长上升子序列的长度为3 可能的最长上升子序列的有{4,5,6} 与 {1,2,3} 因此，有6个位置上的元素可能出现在最长上升子序列中，有0个位置上的元素一定出现在最长上升子序列中。

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐。

测试点分布