在数组中找到一个子数组，其元素之和乘以该子数组中的最小元素会产生最大值

Question

我需要创建一个算法，该算法采用数组A作为参数，并找到A的一个子数组，其元素之和乘以该子数组中的最小元素会产生最大值。A中的值为正数，我们无法更改该数组中的顺序。

有人告诉我可以在 O(nlogn) 内完成。我正在考虑某种分而治之的算法来服从暴力方法。

有任何想法吗？

Answer 1

我们可以O(n log n)通过评估来进行分而治之：

f(whole_section) =
  max(
    f'(whole_section),
    f(left_half),
    f(right_half)
  )

其中f'计算一个部分的最大值，该部分至少包括左侧的一个元素和右侧的一个元素（或者在奇数整个部分的情况下至少包括单个中间元素）。

要了解如何f'计算，O(n)请考虑以下示例。下面说的是和g中较小的一个。gh

abcdefghijklmn
      ^^

向两个方向扩展间隔，直到g遇到下一个小于该值的元素。

abcdefghijklmn
    ^    ^

现在Sayj是下一个最小的（e小于所以我们在左侧j结束当前间隔）。f

O(1)每次移动指针时，我们的总和和乘数都会更新。再次计算g * sum并扩大间隔，这次为j最小。j请注意，指针可以沿任一方向传递多个值。

abcdefghijklmn
    ^      ^

l这次是下一个更小的时间j，e甚至更小。计算j * sum并继续。

由于区间扩展期间的每个元素最多被访问一次，f'因此可以在 中求值O(n)，并且由于我们通过每次递归调用将元素数量减半f，f因此可以在 中求值O(n log n)。