#include #include #include #include using namespace std; int main(void){ // Here your code ! int T; cin >> T; for(int t=0;t> N; vector as; as.push_back(0); for(int i=0;i> val; as.push_back(val); } as.push_back(0); vector> leftdp(N+2, vector(N+2, INT_MAX)); vector leftmax(N+2, 0); vector> rightdp(N+2, vector(N+2, INT_MAX)); vector rightmax(N+2, 0); //leftdp[0][0]=0; for(int i=1;i<=N;i++){ leftdp[i][1]=0; rightdp[i][1]=0; leftmax[i]=1; rightmax[i]=1; } for(int i=1;i<=N;i++){ for(int j=1;j leftdp[j][k]){ // printf("i=%d, j=%d, k=%d, as[i]=%d, as[j]=%d\n", i, j, k, as[i], as[j]); leftdp[i][k+1] = min(leftdp[i][k+1], as[i] - as[j]); leftmax[i] = max(leftmax[i], k+1); } } } } // rightdp[N+1][0]=0; for(int i=N;i>=1;i--){ for(int j=N;j>i;j--){ for(int k=0;k rightdp[j][k]){ // printf("i=%d, j=%d, k=%d, as[i]=%d, as[j]=%d\n", i, j, k, as[i], as[j]); // printf("i=%d, j=%d, k=%d\n", i, j, k); rightdp[i][k+1] = min(rightdp[i][k+1], as[i] - as[j]); rightmax[i] = max(rightmax[i], k+1); } } } } int final = 0; for(int i=1;i<=N;i++){ // printf("leftmax[%d]=%d, rightmax[%d]=%d\n", i, leftmax[i], i, rightmax[i]); int m = leftmax[i] + rightmax[i]-1; final = max(final, m); } cout << final << endl; } return 0; }