Cip*_*ext 5 algorithm math median
这是一个算法问题：
输入是具有非重复正整数的数组。查找具有最大中值的连续子数组（大小> 1）。
示例：输入：[100、1、99、2、1000]，输出应为（1000 + 2）/ 2 = 501的结果
我可以提出强力解决方案：尝试从2->数组大小的所有长度中找到最大中值。但这似乎太慢了。我也尝试在此问题上使用两个指针，但不确定何时向左和向右移动指针。
有谁有更好的主意来解决这个问题？
tl; dr-我们可以证明答案的长度必须为2或3，在此之后是检查所有可能性的线性时间。
假设输入为A，而中位数最大的最小子数组为a。中位数最大的是中的一个元素或一对元素的平均值a。请注意，a大于中位数最大元素的每个元素只能与小于中位数最小元素的元素相邻（否则，可以选择这样的一对作为子数组以形成更大的中位数）。
如果的任一端a都有一对不包含中位数元素的元素，则可以在a不影响中位数的情况下消除这一矛盾。
如果的任一端a小于中位数的最小元素，则消除它会增加中位数，这是一个矛盾。
因此，的每个末端a要么是中位数的一个元素，要么大于中位数的最大元素（因为它大于中位数的最小Elt，但不等于中位数的最大Elt）。
因此，的每个末端a都是中位数的一个元素，因为否则，我们将拥有一个比中位数的Elt相邻的中位数更大的元素，从而形成更大的中位数。
如果a为奇数，则它的长度必须为三，因为任何较大的奇数长度都可以从a距离中位数最远的一端删除2，而不会更改中位数。
如果a是，则它的长度必须为2，因为由中位数的元素预定的任何更大的偶数长度，且内部元素在中位数与中位数之间交替变化时，中位数元素之一必须比另一元素的相邻元素大。中位数，形成更大的中位数。
该证明大纲可以使用一些编辑，但是无论如何，得出的结论是，包含最大中位数的最小数组的长度必须为2或3。
鉴于此，请在线性时间内检查每个此类子数组。上）。