如何计算数组中的最大中位数

tl; dr-我们可以证明答案的长度必须为2或3，在此之后是检查所有可能性的线性时间。

假设输入为A，而中位数最大的最小子数组为a。的最大中位数是的单个元素或一对元素的平均值a。请注意，a大于中位数最大元素的每个元素只能与小于中位数最小元素的元素相邻（否则，可以选择这样的一对作为子数组以形成更大的中位数）。

如果的任一端a都有一对不包含中位数元素的元素，则可以在a不影响中位数的情况下消除这一矛盾。

如果的任一端a小于中位数的最小元素，则消除它会增加中位数，这是一个矛盾。

因此，的每个末端a要么是中位数的一个元素，要么大于中位数的最大元素（因为它大于中位数的最小Elt，但不等于中位数的最大Elt）。

因此，的每个末端a都是中位数的一个元素，因为否则，我们将有一个元素大于与中位数Elt相邻的中位数的元素，从而形成更大的中位数。

如果a为奇数，则它的长度必须为三，因为任何较大的奇数长度都可以从a距离中位数最远的一端删除2，而不会更改中位数。

如果a是，则它的长度必须为2，因为由中位数的元素预定的任何更大的偶数长度，内部元素在中位数之间交替变小或大于，必须使中位数元素中的一个相邻于比其他元素大的元素。中位数，形成更大的中位数。

该证明大纲可以进行一些编辑，但是无论如何，得出的结论是，包含最大中位数的最小数组的长度必须为2或3。

鉴于此，请在线性时间内检查每个此类子数组。上）。