Solution
Approach 1: Next Array
Intuition
Instead of checking whether all(L <= R for L in left for R in right)
, let's check whether max(left) <= min(right)
.
Algorithm
Let's try to find max(left)
for subarrays left = A[:1], left = A[:2], left = A[:3], ...
etc. Specifically, maxleft[i]
will be the maximum of subarray A[:i]
. They are related to each other: max(A[:4]) = max(max(A[:3]), A[3])
, so maxleft[4] = max(maxleft[3], A[3])
.
Similarly, min(right)
for every possible right
can be found in linear time.
After we have a way to query max(left)
and min(right)
quickly, the solution is straightforward.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: .
Analysis written by: @awice.