Summe der kontinuierlichen Sequenzen - Algorithmus

Gegeben ein Array A mit N Elementen, möchte ich findendie Summe der minimalen Elemente in allen möglichen zusammenhängenden Untersequenzen von A. Ich weiß, wenn N klein ist, können wir nach allen möglichen Untersequenzen suchen, aber da N bis zu 10 ^ 5 ist, was kann der beste Weg sein, um diese Summe zu finden?

Beispiel: Sei N = 3 und A [1,2,3] dann ist ans 10 als Mögliche zusammenhängende Untersequenzen {(1), (2), (3), (1,2), (1,2,3) , (2,3)} so Summe der minimalen Elemente = 1 + 2 + 3 + 1 + 1 + 2 = 10

Antworten:

• Lass uns ein Element fixieren (a[i]). Wir wollen die Position des am weitesten rechts liegenden Elements kennen, das kleiner ist als das links davon i(L). Wir müssen auch die Position des Elements ganz links kennen, das kleiner ist als das, das rechts von ihm liegt i(R).

• Wenn wir es wissen L und R, sollten wir hinzufügen (i - L) * (R - i) * a[i] zur Antwort.

• Es ist möglich, vorauszuberechnen L und R für alle i in linearer Zeit unter Verwendung eines Stapels. Pseudocode:

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

  Wir können das Array umkehren und den gleichen Algorithmus zum Suchen ausführen R.

• Wie mit gleichen Elementen umgehen? Nehmen wir an, dass a[i] ist ein Paar <a[i], i>. Alle Elemente sind jetzt verschieden.

Die zeitliche Komplexität ist O(n).

Hier ist ein voller Pseudocode (ich nehme an, dass int kann einen beliebigen ganzzahligen Wert hier halten, sollten Sie Wählen Sie einen möglichen Typ, um einen Überlauf in einem echten Code zu vermeiden. Ich nehme auch an, dass alle Elemente verschieden sind):

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

Wenn die Liste sortiert ist, können Sie alle Teilmengen für Größe 1, dann 2 und dann 3 bis N berücksichtigen. Der Algorithmus ist anfangs etwas ineffizient, aber eine optimierte Version ist darunter. Hier ist ein Pseudocode.

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

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

Zuerst wird mit einem Element gesetzt: {{1}, {2}, {3}}: summiere jedes der Elemente.

Dann setzen Sätze von zwei Elementen {{1, 2}, {2, 3}}: summieren jedes Element außer dem letzten.

Dann setzen Sätze von drei Elementen {{1, 2, 3}}: summieren jedes Element außer den letzten beiden.

Aber dieser Algorithmus ist ineffizient. Um zu O (n) zu optimieren, multipliziere jedes i-te Element mit N-i und summiere es (hier von Null ausgehend). Die Intuition ist, dass das erste Element das Minimum von N Mengen ist, das zweite Element das Minimum von N-1 Mengen usw.

Ich weiß, es ist keine Python-Frage, aber manchmal hilft Code:

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)