1008. 数字子序列

题目描述

给定一个长度为 n 的数字串 D，其中每一位都是 0 ∼ 9 的数字。一个数字子序列是若干个互不相交且从左到右排列的非空连续子串

D[l1 ..r1 ], D[l2 ..r2 ], …, D[lk ..rk ],

1 ≤ l1 ≤ r1 < l2 ≤ r2 < ⋯ < lk ≤ rk ≤ n

每个被选择的子串按照通常的十进制表示解释为一个整数，数字子序列的长度定义为它包含的整数个数，即上式中的 k。如果一个数字子序列对应的整数序列 x1, x2, …, xk 满足 x1 < x2 <

⋯ < xk 则称它是上升的。请你求出给定数字串 D 的最长上升数字子序

列的长度。

输入格式

第一行输入一个正整数 T (1 ≤ T ≤ 500)，表示数据组数。接下来按如下格式输入 T 组数据：第一行输入一个数字串 D，设 D 的长度为 n，保证 1 ≤ n ≤ 105。保证所有数据中 n 的总和不超过 5 × 105。

输出格式

对于每组数据，输出一行一个整数，表示最长上升数字子序列的长度。

样例输入

1
271828182845904523536028747135266249775724709369995

样例输出

17

提示

对于样例，一种最优方案是选择

2, 7, 8, 18, 28, 45, 52, 53, 60, 287, 471, 526, 624, 977, 5724, 7093, 69995因此答案为 17。

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第1场）