题解

思路推导

设美丽子序列的最后一个元素来自原序列下标 $i$。如果此前一个元素来自下标 $j$，那么必须同时满足 $j\mid i$ 与 $a_j<a_i$。因此可以把问题写成按下标递增的动态规划。

直接对每个 $i$ 枚举全部 $j<i$ 可以得到二次算法。为了处理完整范围，改为从一个下标 $j$ 出发枚举 $2j,3j,\ldots$。这样只访问真正满足位置整除条件的下标对，再根据值的大小决定是否转移。

做法

令 $f_i$ 表示以 $a_i$ 结尾的最长美丽子序列长度，初值均为 $1$。按 $i=1,2,\ldots,n$ 的顺序处理，并枚举 $i$ 的所有更大倍数 $j$。若 $a_i<a_j$，就用 $f_i+1$ 更新 $f_j$。

由于所有转移都从较小下标指向较大下标，处理到 $i$ 时 $f_i$ 已经确定。最终答案是所有 $f_i$ 的最大值。

正确性证明

任意以 $j$ 结尾且长度大于 $1$ 的美丽子序列，其倒数第二个元素位于某个下标 $i<j$，并满足 $i\mid j$ 与 $a_i<a_j$。算法处理 $i$ 时会枚举到倍数 $j$，从而用对应最优状态更新 $f_j$，所以不会漏掉任何合法子序列。

反过来，算法执行的每次转移都满足位置整除和值严格递增。把 $a_j$ 接到取得 $f_i$ 的美丽子序列后仍然合法，因此算法产生的每个状态都能由真实美丽子序列达到。两方面结合，所有 $f_i$ 均为准确最优值，最大者即为答案。

复杂度分析

倍数枚举次数为 $\sum_{i=1}^{n}\lfloor n/i\rfloor=O(n\log n)$。时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。