Somma di sequenze continue - algoritmo

Dato un array A con N elementi, voglio trovarela somma degli elementi minimi in tutte le possibili sottosequenze contigue di A. So che se N è piccolo possiamo cercare tutte le possibili sottosequenze ma come N è fino a 10 ^ 5 quale può essere il modo migliore per trovare questa somma?

Esempio: Sia N = 3 e A [1,2,3] allora ans è 10 come Possibili sequenze secondarie contigue {(1), (2), (3), (1,2), (1,2,3) , (2,3)} così Somma degli elementi minimi = 1 + 2 + 3 + 1 + 1 + 2 = 10

risposte:

• Risolviamo un elemento (a[i]). Vogliamo conoscere la posizione dell'elemento più a destra più piccolo di questo situato a sinistra da i(L). Dobbiamo anche conoscere la posizione dell'elemento più a sinistra più piccolo di questo situato a destra da i(R).

• Se lo sappiamo L e R, dovremmo aggiungere (i - L) * (R - i) * a[i] alla risposta.

• È possibile precomputare L e R per tutti i in tempo lineare usando una pila. Pseudo codice:

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

  Possiamo invertire la matrice ed eseguire lo stesso algoritmo per trovare R.

• Come trattare gli elementi uguali? Supponiamo che a[i] è una coppia <a[i], i>. Tutti gli elementi sono distinti ora.

La complessità del tempo è O(n).

Ecco un codice pseudo completo (presumo che int può contenere qualsiasi valore intero qui, dovresti scegli un tipo fattibile per evitare un overflow in un codice reale. Suppongo anche che tutti gli elementi siano distinti):

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

Se l'elenco è ordinato, puoi considerare tutti i sottoinsiemi per la dimensione 1, quindi 2, quindi 3, per N. L'algoritmo inizialmente è in qualche modo inefficiente, ma una versione ottimizzata è inferiore. Ecco alcuni pseudocodici.

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

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

Per prima cosa, imposta con un elemento: {{1}, {2}, {3}}: somma ciascuno degli elementi.

Quindi, set di due elementi {{1, 2}, {2, 3}}: somma ogni elemento tranne l'ultimo.

Quindi, set di tre elementi {{1, 2, 3}}: somma ogni elemento ma gli ultimi due.

Ma questo algoritmo è inefficiente. Per ottimizzare a O (n), moltiplicare ciascun elemento ith per N-i e sum (indicizzazione da zero qui). L'intuizione è che il primo elemento è il minimo di N set, il secondo elemento è il minimo di set N-1, ecc.

So che non è una domanda pitone, ma a volte il codice aiuta:

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)