F 求hack数据

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <math.h>
#include <map>
#include <set> 
#include <queue>
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10, mod = 1e17 + 7;

int n, m, k;
int a[N], s[N];
int ans[N];
int pre[N], ed[N]; //前后缀最小值

void solve() 
{
    cin >> n;
    for(int i = 0; i <= n + 1; i++) ans[i] = 0, pre[i] = mod, ed[i] = mod;
    for(int i = 1; i <= n; i++) cin >> a[i], s[i] = s[i - 1] + a[i];
    
    pre[0] = ed[n + 1] = mod; //极值
    for(int i = 1; i <= n; i++) pre[i] = min(pre[i - 1], a[i]);
    for(int i = n; i >= 1; i--) ed[i] = min(ed[i + 1], a[i]);
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = i; j <= n; j++)
        {
            int len = j - i + 1;
            if(len == n) continue;
            int sum = s[j] - s[i - 1];
            //区间最小值 O(1) 时间
            int res = sum - min(pre[i - 1], ed[j + 1]);
            ans[len - 1] = max(ans[len - 1], res);
        }
    }
    
    for(int i = 0; i < n; i++) cout << ans[i] << " ";
    cout << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) 
    {
        solve();
    }
    return 0;
}