最长递增子序列问题

Description:

 

 给定正整数序列x₁ , …, x _n。

（1）计算其最长递增子序列的长度s。

（2）计算从给定的序列中最多可取出多少个长度为s的递增子序列。

（3）如果允许在取出的序列中多次使用x₁和x _n，则从给定序列中最多可取出多少个长度为s的递增子序列。

设计有效算法完成（1）（2）（3）提出的计算任务。

Input:

       第1行有1个正整数n，表示给定序列的长度。接下来的1行有n个正整数  x₁ , …, x _n。

Output:

 

第1 行是最长递增子序列的长度s。第2行是可取出的长度为s 的递增子序列个数。第3行是允许在取出的序列中多次使用x₁和x _n时可取出的长度为s 的递增子序列个数。

Sample Input:

4
3 6 2 5

Sample Output:

2
2
3

Note:

 

本题由旧版NOJ导入，来源： 算法设计与实验题解