#P17898. One Permutation
One Permutation
题目描述
给定一个长度为 的排列 。
定义一个连续子段的代价,为该子段的最长严格递增子序列的长度。子序列可以删除元素,但剩余元素必须保持原来的相对顺序,不要求位置连续。
将整个排列划分为 个非空、互不相交的连续子段,划分的代价为这些子段的代价之和。
记 为所有这样的划分中,代价的最大值。请计算 。
输入格式
第一行包含整数 ,表示测试用例数。
每个测试用例第一行包含整数 ,第二行包含排列 。
输出格式
对每个测试用例输出一行 个整数,依次表示 。
数据范围
- ;
- ;
- 是 到 的排列;
- 一个输入文件内所有测试用例的 之和不超过 。
样例输入
3
3
1 2 3
3
3 2 1
4
2 1 4 3
样例输出
3 3 3
1 2 3
2 3 4 4
样例解释
第三个测试用例中,划分成两个子段 与 ,其最长递增子序列长度分别为 和 ,总和为 。