Suma ciągłych sekwencji

Question

Biorąc tablicę A z N elementami, chcę znaleźć sumę minimalnych elementów we wszystkich możliwych ciągłych podsekcjach A. Wiem, że jeśli N jest małe, możemy szukać wszystkich możliwych podsekwencji, ale jak N jest upto 10^5 jaki może być najlepszy sposób na znalezienie tej sumy?

Przykład: Niech N = 3 i A [1,2,3] to ans jest 10 jako Możliwe ciągłe podsekcje {(1), (2), (3), (1,2), (1, 2,3), (2,3)} więc Suma minimalnych elementów = 1 + 2 + 3 + 1 + 1 + 2 = 10

Answer 1

Jeśli lista jest posortowana, można rozważyć wszystkie podzbiory dla rozmiaru 1, a następnie 2, a następnie 3, do N. Algorytm jest początkowo nieco nieefektywny, ale zoptymalizowana wersja znajduje się poniżej. Oto pseudokod.

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

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

Najpierw wyznacza się jeden z elementów: {{1}, {2}, {3}}: suma wszystkich elementów.

Następnie, zestawy dwóch elementów {{1, 2}, {2, 3}}: sumują każdy element, ale ostatni.

Następnie zestawy trzech elementów {{1, 2, 3}}: sumują każdy element oprócz dwóch ostatnich.

Ale ten algorytm jest nieefektywny. Aby zoptymalizować do O (n), pomnóż każdy element ith przez N-i i sumę (indeksowanie od zera tutaj). Intuicja jest to, że pierwszy element jest minimalna zestawów N, drugi element jest minimalna N-1 zbiorów itp

wiem, że to nie jest kwestia Python, ale czasami kod pomaga:

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) 

Answer 2

• Naprawmy jeden element (a[i]). Chcemy znać położenie najbardziej wysuniętego na prawo elementu mniejszego niż ten znajdujący się po lewej stronie od i (L). Musimy również znać pozycję najbardziej wysuniętego na lewo elementu mniejszego niż ten znajdujący się po prawej stronie od i (R).

• Jeśli znamy L i R, powinniśmy dodać odpowiedź (i - L) * (R - i) * a[i].

• Możliwe jest wstępne obliczenie L i R dla wszystkich i w czasie liniowym za pomocą stosu. pseudokod:

  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)) 
  

  Możemy odwrócić tablicę i uruchomić ten sam algorytm, aby znaleźć R.

• Jak radzić sobie z równymi elementami? Załóżmy, że a[i] to para <a[i], i>. Wszystkie elementy są teraz wyraźne.

Złożoność czasowa to O(n).

Oto pełny kod pseudo (. Zakładam, że int może posiadać dowolną liczbę całkowitą tutaj, należy wybrać realną typu, aby uniknąć przepełnienia w prawdziwym kodzie Zakładam również, że wszystkie elementy są różne):

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