Сума от непрекъснати последователности - алгоритъм

Предвид масив А с елементи N, искам да намерясумата от минималните елементи във всички възможни съседни подсерии на А. Знам, че ако N е малък, можем да търсим всички възможни подсектори, но като N е до 10 ^ 5 какво може да бъде най-добрият начин да се намери тази сума?

Пример: Нека N = 3 и А [1,2,3] след това ans е 10 като Възможни съседни подразделения {(1), (2), (3), (1,2), (1,2,3) , (2, 3)} така Сума от минималните елементи = 1 + 2 + 3 + 1 + 1 + 2 = 10

Отговори:

• Нека оправим един елемент (a[i]). Искаме да знаем позицията на най-десния елемент, по-малък от този, разположен отляво i(L). Също така трябва да знаем позицията на най-левия елемент, по-малък от този, разположен отдясно i(R).

• Ако знаем L и R, трябва да добавим (i - L) * (R - i) * a[i] към отговора.

• Възможно е предварително пресмятане L и R за всички i в линейно време, използвайки стека. Псевдо код:

  s = new Stack
  L = new int[n]
  fill(L, -1)
  for i <- 0 ... n - 1:
  while !s.isEmpty() && s.top().first > a[i]:
  s.pop()
  if !s.isEmpty():
  L[i] = s.top().second
  s.push(pair(a[i], i))
  

  Можем да обърнем масива и да стартираме същия алгоритъм за намиране R.

• Как да се справяме с еднакви елементи? Да предположим това a[i] е двойка <a[i], i>, Сега всички елементи са различни.

Сложността на времето е O(n).

Ето пълен псевдо-код (предполагам, че int може да задържи цялото число тук, трябва изберете подходящ тип, за да избегнете препълване в реален код. Предполагам също, че всички елементи са различни):

int[] getLeftSmallerElementPositions(int[] a):
s = new Stack
L = new int[n]
fill(L, -1)
for i <- 0 ... n - 1:
while !s.isEmpty() && s.top().first > a[i]:
s.pop()
if !s.isEmpty():
L[i] = s.top().second
s.push(pair(a[i], i))
return L

int[] getRightSmallerElementPositions(int[] a):
R = getLeftSmallerElementPositions(reversed(a))
for i <- 0 ... n - 1:
R[i] = n - 1 - R[i]
return reversed(R)

int findSum(int[] a):
L = getLeftSmallerElementPositions(a)
R = getRightSmallerElementPositions(a)
int res = 0
for i <- 0 ... n - 1:
res += (i - L[i]) * (R[i] - i) * a[i]
return res

Ако списъкът е сортиран, можете да разгледате всички подгрупи за размер 1, след това 2, след това 3, за N. Алгоритъмът първоначално е донякъде неефективен, но оптимизираната версия е по-долу. Ето един псевдокод.

let A = {1, 2, 3}
let total_sum = 0

for set_size <- 1 to N
total_sum += sum(A[1:N-(set_size-1)])

Първо, определя с един елемент: {{1}, {2}, {3}}: сумира всеки от елементите.

След това множества от два елемента {{1, 2}, {2, 3}}: сумират всеки елемент, но последния.

След това, множества от три елемента {{1, 2, 3}}: сумират всеки елемент, но последните два.

Но този алгоритъм е неефективен. За да оптимизирате до O (n), умножете всеки i-елемент с N-i и сумата (индексирайки от нула тук). Интуицията е, че първият елемент е минимумът от N сетове, вторият елемент е минималният от N-1 комплекти и т.н.

Знам, че това не е въпрос на питън, но понякога кодът помага:

A = [1, 2, 3]

# This is [3, 2, 1]
scale = range(len(A), 0, -1)

# Take the element-wise product of the vectors, and sum
sum(a*b for (a,b) in zip(A, scale))

# Or just use the dot product
np.dot(A, scale)