答案由两部分组成，一部分为加和，另一部分为 \max。假设我们当前已经确定答案不超过 x，那么有：

• 两个点间的最大间隔不超过 x。
• 点权之和不超过 x。

不妨用前者来约束后者。加入两个虚点 a_0=a_{n+1}=0，设 dp_i 表示考虑前 i 个位置，选了第 i 个位置，且最大间隔不超过 x 的最小价值。容易得到转移：

其中 s 为前缀和数组。显然每次可转移到 i 的区间左右端点都单增，所以可以单调队列优化至线性。

此时 dp_{n+1} 即为答案，若 dp_{n+1}\le x，则表示答案可以 \le x。二分答案即可，时间复杂度 O(n\log nV)。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

int T, n; ll a[MAXN], s[MAXN], dp[MAXN];

deque<int> q;

inline 
bool check(ll x) {
    for (int i = 1; i <= n + 1; i++) dp[i] = 0;
    q.clear(), q.push_back(0);
    for (int i = 1, j = 0; i <= n + 1; i++) {
        for (; !q.empty() && s[i - 1] - s[q.front()] > x; q.pop_front());
        dp[i] = a[i] + dp[q.front()];
        for (; !q.empty() && dp[q.back()] >= dp[i]; q.pop_back());
        q.push_back(i);
    }
    return dp[n + 1] <= x;
}

ll l, r, mid;

int main() {
    for (scanf("%d", &T); T--;) {
        scanf("%d", &n), a[n + 1] = 0;
        for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
        for (l = 1, r = s[n]; l < r; check(mid = l + r >> 1) ? r = mid : l = mid + 1);
        printf("%lld\n", l);
    }
}