Max GEQ Sum -- CF 1691D

Difficulty: 1800 * Techniques: monotonic stack, sparse table, prefix sums Problem Link

Quick Revisit

• PROBLEM: Check if max(subarray) >= sum(subarray) for every subarray
• KEY INSIGHT: Fix the max element, find its domain via monotonic stack, then check max subarray sum in that domain
• TECHNIQUES: monotonic stack, sparse table (range max/min), prefix sums
• TRANSFER: "For every subarray, property P holds" -- iterate over the controlling element, not over subarrays

First Read

We have an array $a$ of length $n$. For every subarray $a[l..r]$, the condition $max(a[l..r])\ge a[l]+a[l+1]+\dots +a[r]$ must hold. We need to check if this is true.

My brain immediately goes: "Wait, max of a subarray is always at most the sum when elements are non-negative." So this only gets interesting with negative numbers. The max is always one of the elements. So really, the question is: for every element $a[i]$, is $a[i]\ge$ the sum of every subarray where $a[i]$ is the maximum?

That reframing is everything. We don't iterate over subarrays -- we iterate over elements as potential maximums.

Wrong Turn: Sliding Window

My first instinct was some kind of two-pointer or sliding window approach -- expand a window, track max and sum, check the condition. But the max changes discontinuously as the window moves. You can't maintain it efficiently in a plain sliding window. And there are $O(n^2)$ subarrays, so brute force is dead on $n\le 2\times {10}^5$.

The Breakthrough

For each element $a[i]$, I need to know: what's the farthest left and right I can go while $a[i]$ remains the maximum? That's exactly what a monotonic stack gives me -- the previous and next greater-or-equal element.

Once I know the range $[L_i,R_i]$ where $a[i]$ is the max, the worst case for the condition is the maximum subarray sum within that range that includes position $i$. So I need max prefix sum to the right of $i$ in $[i,R_i]$ and max suffix sum to the left of $i$ in $[L_i,i]$.

Prefix sums + sparse table for range-max queries on prefix sums. That's it.

Building It

1. Compute prefix sums $P[0..n]$ where $P[i]=a[1]+\dots +a[i]$.
2. Build a sparse table on $P$ for range-max queries.
3. Use a monotonic stack to find, for each $i$, the boundaries $L_i$ and $R_i$ where $a[i]$ is the maximum.
4. For each $i$: the max subarray sum through $i$ in range $[L_i,R_i]$ equals $\underset{j\in [i,R_i]}{max}P[j]-\underset{k\in [L_i-1,i-1]}{min}P[k]$. We need a sparse table for range-max and range-min on prefix sums.
5. Check if that max subarray sum exceeds $a[i]$.

Implementation Notes

• Tie convention. When two elements are equal, both could claim "I am the max of this subarray." We only want one representative per equal group, otherwise we'd test the same subarray twice with different anchors and could miss subarrays at the boundary. The standard fix is asymmetric: pop on < (strict) when sweeping for the left boundary and on <= when sweeping for the right (or vice versa). Equal elements get assigned consistently to the leftmost (or rightmost) of the group, so each subarray has exactly one anchor.

• Prefix-sum indexing. $P[0]=0$, and the sum of $a[l..r]$ (1-indexed inclusive) is $P[r]-P[l-1]$. In 0-indexed code, the sum of $a[l..r]$ is $P[r+1]-P[l]$. When element $a[i]$ (0-indexed) is the max on range $[L_i,R_i]$, the max subarray sum through $i$ is

  $$\underset{j\in [i,R_i]}{max}P[j+1]-\underset{k\in [L_i,i]}{min}P[k].$$

  In code that becomes mx.query(i + 1, R[i] + 1) - mn.query(L[i], i). The right query starts at i+1 because the subarray must include position i; the left query ends at i because P[i] represents "sum before index i."

• We need two sparse tables: one for max of prefix sums, one for min of prefix sums.

Tiny dry run

a = [-1, 2, -1]. Prefix sums $P=[0,-1,1,0]$.

Take $i=1$ (the value 2). Both stack passes give $L_1=0$, $R_1=2$ (it's the global max). Then:

• mx.query(2, 3) = $max(P[2],P[3])$ = $max(1,0)$ = 1.
• mn.query(0, 1) = $min(P[0],P[1])$ = $min(0,-1)$ = $-1$.
• best subarray sum through index 1 = $1-(-1)=2$.

Compare to $a[1]=2$: $2\ngtr 2$, so the condition holds. Trying any other anchor confirms Yes.

The Code

#include <bits/stdc++.h>
using namespace std;

struct SparseTable {
    vector<vector<long long>> tb;
    int flag; // 1 = max, -1 = min
    SparseTable() {}
    SparseTable(vector<long long>& a, int f) : flag(f) {
        int n = a.size(), LOG = __lg(n) + 1;
        tb.assign(LOG, vector<long long>(n));
        tb[0] = a;
        for (int k = 1; k < LOG; k++)
            for (int i = 0; i + (1 << k) <= n; i++)
                tb[k][i] = (flag == 1) ? max(tb[k-1][i], tb[k-1][i + (1 << (k-1))])
                                       : min(tb[k-1][i], tb[k-1][i + (1 << (k-1))]);
    }
    long long query(int l, int r) { // [l, r]
        int k = __lg(r - l + 1);
        return (flag == 1) ? max(tb[k][l], tb[k][r - (1 << k) + 1])
                           : min(tb[k][l], tb[k][r - (1 << k) + 1]);
    }
};

void solve() {
    int n; cin >> n;
    vector<long long> a(n), pre(n + 1, 0);
    for (int i = 0; i < n; i++) { cin >> a[i]; pre[i+1] = pre[i] + a[i]; }

    SparseTable mx(pre, 1), mn(pre, -1);

    vector<int> L(n), R(n);
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) st.pop();
        L[i] = st.empty() ? 0 : st.top() + 1;
        st.push(i);
    }
    while (!st.empty()) st.pop();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && a[st.top()] <= a[i]) st.pop();
        R[i] = st.empty() ? n - 1 : st.top() - 1;
        st.push(i);
    }

    for (int i = 0; i < n; i++) {
        long long best = mx.query(i + 1, R[i] + 1) - mn.query(L[i], i);
        if (best > a[i]) { cout << "No\n"; return; }
    }
    cout << "Yes\n";
}

int main() {
    int t; cin >> t;
    while (t--) solve();
}

Transfer Lesson

• "For every subarray, some property holds" -- don't iterate subarrays. Fix the controlling element (the max, the min) and find its domain with a monotonic stack.
• Max subarray sum in a range -- think prefix sums + sparse table for range-max/min, not Kadane's (Kadane doesn't support arbitrary ranges).
• Two sparse tables (max and min of prefix sums) is a common duo for subarray sum queries.

---

See also: Monotonic Stack | Sparse Table / RMQ | Prefix Sums | Pattern Recognition Guide | Practice Ladder 1700-2100