<p>It's seems possible to make the brute force approach run fairly quickly.</p>

<p>If you preprocess each sequence into a balanced tree where each node is augmented with the min of that subtree, then you can find the min of any subrange of that sequence in O(log n) time by splitting the tree at the appropriate points. See, for example, <a href="https://arxiv.org/abs/1612.05665" rel="nofollow noreferrer">this paper</a> for more information. Note that this preprocessing takes O(n) time.</p>

<p>Let's call the range (i,j) a <em>window</em>. The complexity of this problem doesn't depend on the specific (i,j), but rather the size of the window (that is, j-i+1). For a window size of m (=j-i+1), there are n-m+1 windows of that size. For each window, there are m+1 places where you can "cut" the window so that some prefix of the elements come from from sequence <code>a</code> and the suffix comes from sequence <code>b</code>. You pay O(log n) for each cut (to split the binary trees as I mentioned above). That's a total cost of <strong>O((n-m+1) * (m+1) * log(n)).</strong></p>

<p>There is probably a faster way to do this, by reusing splits, or by noticing that nearby windows share a lot of elements. But regardless, I think the binary tree splitting trick I mentioned above might be helpful!</p>
algorithm of finding max of min in any range for two arrays
<p>Let's say we have two arrays of ints of equal length, <code>a_1, ..., a_n</code> and <code>b_1, ..., b_n</code>. For any given index pairs <code>i</code> and <code>j</code> with <code>1&lt;=i&lt;j&lt;=n</code>, we need to find the max of the min for any sequence of the form <code>a_k, ..., a_{l-1}, b_l, ..., b_{j-i+k}</code> with <code>0&lt;=k&lt;=n-j+i</code> and <code>l</code> can be <code>j-i+k+1</code>, i.e. that sequence is purely from array <code>a</code>. When <code>k=0</code>, the sequence is purely from array <code>b</code>.</p>

<p>We want to do this for all pairs of <code>i</code> and <code>j</code> very efficiently.</p>

<p>Example, given </p>

<pre><code>`a=[3,2,4,1]` and `b=[4,6,1,3]`
when `i=1, j=3`, the sequence can be
`[3,2,4]`, min is 2
`[3,2,1]`, min is 1
`[3,6,1]`, min is 1
`[2,4,1]`, min is 1
`[2,4,3]`, min is 2
`[2,1,3]`, min is 1
`[4,6,1]`, min is 1
`[6,1,3]`, min is 1
</code></pre>

<p>So the max is 2 for this input.</p>

<p>Is there a good way to run this efficiently?</p>