arrays - 拆分数组并找到最大值 |max (L) -max (R)|

Question

我有一个关于编程的一般性问题。假设我有一个数组，我需要找到将数组分为 L、R 两部分的索引 K，以便值|最大(左)-最大(右)|是最大的。

• max(L)是L部分中最大的数
• K指向R中的第一个成员

Answer 1

这似乎是一个减少到只有 2 个可行候选解的问题:要么 K 将第一个值从其余值中分离出来，要么将最后一个值从其余值中分离出来，给你一个小的一部分只是一个值，大部分是其余值，包括最大值。

假设数组中的最大值可以在索引 M 处找到，那么两个部分之一将具有该值，并且它将是 Max(Part)。另一部分应该有一个尽可能小的最大值。因此，该部分应该减少到只有一个值:向该部分再增加一个值永远不会减少其最大值。

如果整体最大值位于数组的一端，则别无选择，小部分将从数组的另一端切掉。 p>

当整体最大值不在数组的末尾时，有两种可能性:选择截断值最低的那个。换句话说，K 将是 1 或 n-1(在从零开始的索引中)，这可以在常数时间内确定，即 O(1)。