Max GEQ Sum
Contest: CodeCraft-22 and Codeforces Round 795 (Div. 2)
Difficulty rating: 1800
Tags: binary search, constructive algorithms, data structures, divide and conquer, implementation, two pointers

You are given an array $$$a$$$ of $$$n$$$ integers. You are asked to find out if the inequality $$$$$$\max(a_i, a_{i + 1}, \ldots, a_{j - 1}, a_{j}) \geq a_i + a_{i + 1} + \dots + a_{j - 1} + a_{j}$$$$$$ holds for all pairs of indices $$$(i, j)$$$, where $$$1 \leq i \leq j \leq n$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)  — the size of the array.

The next line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, on a new line output "YES" if the condition is satisfied for the given array, and "NO" otherwise. You can print each letter in any case (upper or lower).

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
In test cases $$$1$$$ and $$$2$$$, the given condition is satisfied for all $$$(i, j)$$$ pairs.

In test case $$$3$$$, the condition isn't satisfied for the pair $$$(1, 2)$$$ as $$$\max(2, 3) < 2 + 3$$$.

Example input:
3
4
-1 1 -1 2
5
-1 2 -3 2 -1
3
2 3 -1

Example output:
YES
YES
NO

Editorial:
Let's look at the problem from the perspective of each $$$a_i$$$. We want to check whether the sum of the subarrays, where $$$a_i$$$ is the maximum element, exceeds $$$a_i$$$ or not.
Firstly, we must find out in which subarrays is $$$a_i$$$ the maximum. This involves finding the previous greater element index and the next greater element index of $$$i$$$, which can be done for all indices in $$$O(n)$$$ using stacks. Take these indices as $$$x_i$$$, $$$y_i$$$. After computing this for every index, we'll know that $$$a_i$$$ is max in subarrays with starting index $$$[x_i + 1, i]$$$ and ending index $$$[i, y_i - 1]$$$.
Take $$$(j, k)$$$, which represents the sum of a subarray which starts at index $$$j$$$ and ends at index $$$k$$$, where $$$j \in [x_i + 1, i]$$$, $$$k \in [i, y_i - 1]$$$. If $$$(j, k) > a_i$$$, then $$$(j, i - 1) + (i, i) + (i + 1, k) > a_i$$$, giving us $$$(j, i - 1) + (i + 1, k) > 0$$$. Hence, at least one of the subarrays, $$$(j, i - 1)$$$ or $$$(i + 1, k)$$$ has a sum greater than $$$0$$$, which implies that one of subarrays $$$(j, i)$$$, $$$(i, k)$$$ has sum greater than $$$a_i$$$, so only checking subarrays which start or end at index $$$i$$$ suffices.
Therefore, for an index $$$i$$$, we need to check subarrays $$$(x_i + 1, i), (x_i + 2, i), \dots, (i - 1, i)$$$, and subarrays $$$(i, i + 1), (i, i + 2), \dots, (i, y_i - 1)$$$. Since we just care if any one of them exceed $$$a_i$$$, finding the max of them is enough. This reduces to making a range query over the prefix sums and one over the suffix sums. The query on prefix sums would look like
$$$$$$ \text{max}(i, y_i - 1) - \text{prefix}[i - 1] > a_i $$$$$$
Where $$$\text{max}(i, y_i - 1)$$$ returns the max prefix sum in the given range. This query can be done using a segment tree in $$$O(\log n)$$$. If any of the queries is true, then we just have to output "NO", else output "YES".
With this we get the time complexity of the solution as $$$O(n\log n)$$$.