max Summe der Listenelemente jeweils getrennt durch (mindestens) k Elemente

Question

gegeben eine Liste von Zahlen, um die maximale Summe nicht benachbarter Elemente mit Zeit Komplexität o (n) und Raumkomplexität von o (1) zu finden, könnte ich verwenden diese:

sum1= 0 
sum2= list[0] 

for i in range(1, len(list)): 
    num= sum1 
    sum1= sum2+ list[i] 
    sum2= max(num, sum2) 

print(max(sum2, sum1)) 

dieser Code funktioniert nur, wenn die k = 1 [nur ein Element zwischen den summierenden Zahlen], wie es durch Ändern k-Wert unter Verwendung einer dynamischen Programmierung verbessern könnte. wobei k die Anzahl der Elemente zwischen den Summierungszahlen ist. zum Beispiel:

list = [5,6,4,1,2] k = 1 answer = 11 # 5 + 4 + 2

list = [5,6,4,1,2 ] k = 2 answer = 8 # 6 + 2

list = [5,3,4,10,2] k = 1 answer = 15 # 5 + 10

Answer 1

Hier ist eine schnelle Implementierung des Algorithmus beschrieben von Ami Tavory (soweit ich es verstehe). Es sollte für jede Sequenz funktionieren, obwohl, wenn Ihre Liste alle negativ ist, die maximale Summe 0 (die Summe einer leeren Subsequenz) ist.

import collections 

def max_sum_separated_by_k(iterable, k): 
    best = collections.deque([0]*(k+1), k+1) 
    for item in iterable: 
     best.appendleft(max(item + best[-1], best[0])) 
    return best[0] 

Dieser verwendet O(k) Raum und O(N) Zeit. Alle deque-Operationen, einschließlich des Anhängens eines Werts an ein Ende (und implizit eines Entfernens vom anderen Ende, so dass die Längenbeschränkung beibehalten wird) und des Lesens von den Enden, sind O(1).

Wenn Sie den Algorithmus soll die maximale Teilfolge zurückzukehren (anstatt ihre Summe nur) können Sie die Initialisierung des deque ändern mit leeren Listen zu beginnen, anstatt 0 und dann max([item] + best[-1], best[0], key=sum) im Körper der Schleife anhängen. Das wird jedoch ein wenig weniger effizient sein, da es O(N) Operationen überall hinzufügt.

Answer 2

EDIT: hatte ich mißverstanden Die Frage, ob Sie "atleast" k Elemente dazwischen haben müssen, ist eine O(n^2) Lösung.

Wenn die Zahlen nicht negativ ist, dann ist die DP-Rekursion ist:

DP[i] = max (DP[j] + A[i]) For all j st 0 <= j < i - k 
     = A[i] otherwise. 

Wenn es negative Zahlen in der Matrix als auch, dann können wir die Idee von Kadane-Algorithmus verwenden:

DP[i] = max (DP[j] + A[i]) For all j st 0 <= j < i - k && DP[j] + A[i] > 0 
     = max(0,A[i]) otherwise. 

Answer 3

Es ist möglich, diese O (k) mit Platz O (nk) und Zeit zu lösen. wenn k eine Konstante ist, entspricht dies den Anforderungen in Ihrer Frage.

Der Algorithmus Schleifen von Position k + 1 zu n. (Wenn das Array kürzer ist, kann es offensichtlich in O (k) gelöst werden). Bei jedem Schritt unterhält sie ein Array best der Länge k + 1, derart, dass der j ten Eintrag von best die beste Lösung gefunden wird, so weit, so dass das letzte Element es verwendet wird, ist mindestens j auf dem links von der aktuellen Position.

best Initialisierung wird durch Setzen erfolgt, um seinen Eintritt j, der größten nicht-negativen Eintrag in dem Array in Positionen 1, ..., k + 1 - j. So zum Beispiel ist der größte best[1] nicht negativer Eintrag in Positionen 1, ..., k und best[k + 1] ist 0.

Wenn an Position i des Arrays, Element i verwendet wird oder nicht. Wenn es verwendet wird, ist das relevante best bis jetzt best[1], so schreiben Sie u = max(best[1] + a[i], best[1]). Wenn das Element i nicht verwendet wird, verschiebt sich jedes "mindestens" Teil um eins, also für j = 2, ..., k + 1, best[j] = max(best[j], best[j - 1]). Schließlich setzen Sie best[1] = u.

Am Ende des Algorithmus ist die Lösung der größte Artikel in best.

Answer 4

Nicht für die Komplexität sicher, aber Codiereffizienz landete mich mit

max([sum(l[i::j]) for j in range(k,len(l)) for i in range(len(l))]) 

(ersetze ich habe list Variable durch l nicht auf ein Schlüsselwort zu Schritt).