Cyc*_*3x3 5 arrays algorithm optimization subset
\n\n\n给定一个包含 n 个元素的数组：
\n\nd[0], d[1], ..., d[n-1].\n 计算所有连续子数组的最大差值的和 (S)。形式上： S = sum{max{d[l,...,r]} - min{d[l, ..., r}} ,\xe2\x88\x80 0 <= l <= r <\nn
\n
输入：
\n\n4 \n1 3 2 4\n输出：
\n\n12\n解释：
\n\n\n\n\nl = 0；r = 0; 数组：[1] 总和 = max([1]) - min([1]) = 0
\n\nl = 0；r = 1; 数组：[1,3] 总和 = max([1,3]) - min([1,3]) = 3 - 1 = 2
\n\nl = 0；r = 2; 数组： [1,3,2] sum = max([1,3,2]) - min([1,3,2]) = 3 - 1\n = 2
\n\nl = 0;r = 3; 数组: [1,3,2,4] sum = max([1,3,2,4]) - min([1,3,2,4]) =\n 4 - 1 = 3
\n\nl = 1；r = 1 将导致零
\n\nl = 1；r = 2; 数组：[3,2] sum = max([3,2]) - min([3,2]) = 3 - 2 = 1；
\n\nl = 1；r = 3; 数组： [3,2,4] sum = max ([3,2,4]) - min([3,2,4]) = 4 -\n 2 = 2;
\n\nl = 2；r = 2; 将导致零
\n\nl = 2; r = 3; 数组：[2,4] sum = max([2,4]) - min([2,4]) = 4 -2 = 2;
\n\nl = 3; r = 3 将导致零；
\n\n总和 = 12
\n
我的想法： \n暴力检查所有可能的子集；传染阵。
\n\nHow to optimize it for larger number?\n这可以在线性时间内完成！对于每个其最大值的子数组，每个元素都会进入总和一次，并且对于其最小值的每个子数组，每个元素都会被减去一次。我们需要一个线性时间算法来查找每个元素是多少个子数组的最大值或最小值，并且我们可以通过对所有最接近的较小值算法进行较小的修改来实现这一点。
这个想法是，为了找到一个元素最多有多少个子数组，我们保留一个我们所看到的大于我们所看到的所有后续元素的元素的堆栈，以及这些数字的位置。当我们找到一个比栈上最后一个元素大的元素时，我们就知道子数组可以向栈顶元素的左侧或右侧延伸多远，并且仍然是最大值，我们可以用它来确定它最多有多少个子数组。我们可以通过简单地否定数组的所有元素来处理最小值。
def max_sums(d):
stack = [(-1, float('inf'))]
sum_ = 0
for i, x in enumerate(d):
while x > stack[-1][1]:
prev_i, prev_x = stack.pop()
prev_prev_i, prev_prev_x = stack[-1]
sum_ += prev_x * (i - prev_i) * (prev_i - prev_prev_i)
stack.append((i, x))
while len(stack) > 1:
prev_i, prev_x = stack.pop()
prev_prev_i, prev_prev_x = stack[-1]
sum_ += prev_x * (len(d) - prev_i) * (prev_i - prev_prev_i)
return sum_
def max_differences_sum(d):
return max_sums(d) + max_sums([-x for x in d])
这是该算法的运行示例。假设输入是[30, 10, 40, 20]. 然后为了计算所有子数组的最大值之和，我们按如下方式迭代输入：
30
我们将这对推(0, 30)入堆栈。堆栈现在记录我们在索引 0 处看到了 30。
10
30 > 10，所以我们将这对推(1, 10)入堆栈。堆栈现在记录我们在索引 1 处看到了 10。
40
10 < 40，因此最大 10 的子数组不能包含该元素。我们看到，最大为10的子数组必须在索引30之后开始，在索引40之前结束，因此它有1个可能的左端点和1个可能的右端点，并且存在1*1这样的数组。我们添加10*1*1总和并(1, 10)从堆栈中弹出。现在总和是 10。
30 < 40，因此 max 30 的子数组也不能包含该元素。我们看到最大为 30 的子数组必须从索引 0 开始并以索引 0 或索引 1 结束，因此存在1*2这样的数组。我们添加30*1*2总和并弹出(0, 30)。现在总和是 70。
堆栈现在是空的，所以我们压入(2, 40)。
20
40 > 20，所以我们推动(3, 20)。
我们已经迭代了所有输入，因此对于(i, x)仍在数组上的任何对，具有 max 的子数组x可以从索引i到数组末尾的任何位置结束，并且可以从前i一个堆栈条目的索引（或如果没有先前的条目，则为数组）。
(3, 20)位于其下方的堆栈上(2, 40)，因此具有 max 的子数组20必须从索引 3 开始和结束。我们将其添加20*1*1到 sum 和 pop 中(3, 20)。现在总和是 90。
(2, 40)位于堆栈上，其下方没有任何内容，因此具有 max 的子数组40可以从任何索引 <= 2 开始，并以任何索引 >= 2 结束。我们将其添加40*3*2到总和并清空堆栈。现在总和是 330。
我们已经考虑了总和中的所有积极项。为了减去最小值，我们否定所有输入元素并再次将它们输入上述算法。我们最终减去 170，总共为 160。