Это можно сделать в линейном режиме! Каждый элемент переходит в сумму один раз для каждого подмассива, который является максимальным, и каждый элемент вычитается один раз для каждого подмассива, это минимум. Нам нужен алгоритм с линейным временем для определения количества подмассивов, каждый из которых является максимальным или минимальным, и мы можем сделать это с незначительной модификацией алгоритма all nearest smaller values.
Идея состоит в том, чтобы найти, сколько подмассивов является элементом max, мы сохраняем стек элементов, которые мы видели, которые больше всех последующих элементов, которые мы видели, вместе с позициями этих чисел , Когда мы находим элемент, который больше, чем последний элемент в стеке, мы знаем, как далеко может быть Subarray слева или справа от элемента в верхней части стека и по-прежнему иметь максимальный размер, и мы можем использовать его для определить, сколько подмассивов - это максимум. Мы можем справиться с минимумами, просто отрицая все элементы массива.
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]. Затем вычислить сумму Maxes всех подрешеток, мы перебирать вход следующим образом:
30
Нажимает пару (0, 30) в стек. Теперь стек записывает, что мы увидели 30 с индексом 0.
10
30 > 10, поэтому мы помещаем пару (1, 10) в стек. Теперь стек записи, которые мы увидели 10 с индексом 1.
40
10 < 40, так подмассивом с макс 10 не может включать этот элемент. Мы видим, что Subarray с max 10 должен начинаться после индекса 30 и заканчиваться до индекса 40, поэтому он имеет 1 возможную левую конечную точку и 1 возможную правую конечную точку, и есть 1*1 такой массив. Добавим 10*1*1 к сумме и вытащите (1, 10) из стека. Сумма составляет 10.
30 < 40, поэтому подмассив с max 30 также не может включать этот элемент. Мы видим, что подмассив с max 30 должен начинать индексом 0 и заканчиваться либо с индексом 0, либо с индексом 1, поэтому здесь есть 1*2 таких массивов. Добавим 30*1*2 к сумме и напишите (0, 30). Сумма составляет 70.
Стек теперь пуст, поэтому мы нажимаем (2, 40).
20
40 > 20, поэтому мы помещаем (3, 20).
Мы итерация всех входные, так и для любой пары (i, x) еще на массиве, подмассив с максимальным x может закончиться в любом из индекса i до конца массива, и он может начать в любом месте от i к предыдущему индекс стека (или начало массива, если нет предыдущей записи).
(3, 20) находится в стеке с (2, 40) под ним, так подмассивом с макс 20 должен начинаться и заканчиваться на индекс 3. Добавим 20*1*1 к сумме и поп (3, 20). Сумма теперь равна 90.
(2, 40) находится в стеке ни с чем под ним, так подмассивом с макс 40 может начаться в любом индексе < = 2 и заканчивается в любом индексе> = 2. Добавим 40*3*2 к сумме и опустошить стек. Сумма составляет 330.
Мы учли все положительные условия в сумме. Чтобы вычесть минимальные значения, мы отменяем все входные элементы и снова загружаем их по вышеописанному алгоритму. В итоге мы вычитаем 170, для общей суммы 160.
Он может найти min и max в O (1). когда «n» и «r» равны, установите min = max = arr [l], затем, добавив следующий элемент, сравните его с min и max и при необходимости измените их. – splash58
@ splash58 Он может найти min и max of что в O (1)? Все прогоны определенного размера для скользящего окна? Вся проблема? Не стесняйтесь писать альтернативное решение. Я не уверен, что комментарии - это способ объяснить это. –
Я уже писал, что нет необходимости вычислять max и min. Я думаю, что это уменьшает временную оценку – splash58