考虑动态规划，我们可以将 DP 状态设计如下：设 $f_i$ 表示以第 $i$ 个下标结尾的最长优美序列的长度。

我们很容易找到状态转移方程：

那么答案序列的长度就是 $f_1, f_2, \dots, f_n$ 中的最大值。

关于 DP 的复杂度：

• 如果通过枚举倍数进行转移，复杂度为 $O(n \log n)$（根据调和级数的性质）
• 如果通过枚举约数进行转移，复杂度为 $O(n \sqrt{n})$

幸运的是，这两种方法在当前题目中都是可接受的。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int MAXN = 500005;
inline int readint()
{
	int res = 0;
	char c = 0;
	while(!isdigit(c))
		c = getchar();
	while(isdigit(c))
		res = res*10+c-'0', c = getchar();
	return res;	
}
int n,a[MAXN],f[MAXN];

int main()
{
	int T = readint();
	while(T--)
	{
		n = readint();
		for(int i = 1; i<=n; i++)
			a[i] = readint();
		for(int i = 1; i<=n; i++)
			f[i] = 1;
		for(int i = 1; i<=n; i++) 
			for(int j = i*2; j<=n; j += i)
				if(a[i]<a[j])
					f[j] = max(f[j],f[i]+1);
		int ans = 0;
		for(int i = 1; i<=n; i++)
			ans = max(ans,f[i]);
		cout << ans << endl;
	}
	return 0;
}