分析

倒着选区间。

设 \(f(i,k)\) 表示从 \([i,n]\) 中选择 \(k\) 个区间，其中最后一个区间（也就是最长的，最靠近 \(i\) 的区间）的最大值。

当 \(k=1\) 时 \[ f(i,k) = \max{\{ f(i+1,k),a_i \}} \] 当 \(i+k-1 \le n\) 且 \(S(i,i+k-1) < f(i+k,k-1)\) 时 \[ f(i,k) = \max{\{ f(i+1,k),S(i+k,k-1) \}} \] 限制条件是由于

1. 选择包括 \(i\) 在内的长度为 \(k\) 的区间不能越界。
2. \(f(i+k,k-1)\) 实际上就是上一个区间的最大值，要符合题意，\(S(i+k,k-1)\) 这一段和必须严格小于它。

最后倒序枚举 \(k\)，首个非 0 的 \(f(1,k)\) 中的 \(k\) 即为答案。

\(\frac{k(k+1)}{2} \le n\)，是 \(O(\sqrt n)\) 级别的。

复杂度 \(O(n \sqrt n)\)。

CODE

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5, K=505;
const ll inf=1e16;
int t, n, a[N], lim;
ll s[N], f[N][K];
void solve() {
	lim=0;
	scanf("%d",&n);
	for(int i=0;i*(i+1)<=2*n;++i) f[n+1][i]=-inf;
    // 边界
	for(int i=1;i<=n;++i) scanf("%d",&a[i]), s[i]=s[i-1]+a[i];
	for(int i=n;i;--i) for(int k=1;k*(k+1)<=2*n;++k) {
		if((k+1)*(k+2)>2*n) lim=k;
        // 如果成立，表示这个k合法，下一个就不合法了
        // lim记录最大的k，不然开平方会有误差。
		f[i][k]=f[i+1][k];
		ll S=s[i+k-1]-s[i-1];
		if(k==1) f[i][k]=max(f[i][k],1ll*a[i]);
		else if(k&&i+k-1<=n&&S<f[i+k][k-1]) f[i][k]=max(f[i][k],S);
	}
	for(int k=lim;k;--k) if(f[1][k]>0) { printf("%d\n",k); return; }
}
int main() {
	scanf("%d",&t);
	while(t--) solve();
}