Längste subarray, deren Elemente bilden eine kontinuierliche Abfolge

Algorithmus zum lösen ursprüngliche problem in O(n) ohne Duplikate. Vielleicht hilft es jemandem, der Entwicklung in O(n) Lösung, die sich mit Duplikaten.

Eingabe: [a1, a2, a3, ...]

Karte original-array als paar, wo 1. element ist ein Wert, und 2. ist der index des array.

Array: [[a1, i1], [a2, i2], [a3, i3], ...]

Sortieren das array von Paaren mit einigen O(n) Algorithmus (e.g Zählen, Sortieren) für integer-Sortierung von Wert.
Wir haben hier einige ein anderes array:

Array: [[a3, i3], [a2, i2], [a1, i1], ...]

wo a3, a2, a1, ... sind in sortierter Reihenfolge.

Ausführen Schleife über sortierte array von Paaren

In der linearen Zeit, die wir erkennen können aufeinander folgende Gruppen von zahlen, a3, a2, a1. Aufeinanderfolgende Gruppe definition ist der nächste Wert = prev-Wert + 1.
Beim Scannen halten Sie die aktuelle Größe der Gruppe (n), mindestens ein Wert von index (min), und die aktuelle Summe der Indizes (actualSum).

Auf jedem Schritt in aufeinander folgenden Gruppe können wir schätzen die Summe der Indizes, denn Sie schaffen arithmetische progression mit dem ersten element min, Schritt 1, und die Größe der Gruppe bisher gesehen n.
Diese Summe schätzen kann durchgeführt werden in O(1) Zeit mit Hilfe der Formel für die arithmetische progression:

Schätzung Summe = (a1 + an) * n /2;

Schätzung Summe = (min + min + (n - 1)) * n /2;

Schätzung Summe = min * n + n * (n - 1) /2;

Wenn auf einigen Schleife in Schritt aufeinander folgenden Gruppe Schätzung Summe entspricht der tatsächlichen Summe, dann bisher gesehen aufeinanderfolgende Gruppe, die diese Bedingungen erfüllen. Speichern n als aktuelle maximale Ergebnis, oder wählen Sie maximal zwischen aktuellen, maximalen und n.

Wenn auf der Wert-Elemente wir aufhören, aufeinander folgenden Gruppe, dann setzen Sie alle Werte und das gleiche tun.

Code Beispiel: https://gist.github.com/mishadoff/5371821

UPD2: Die folgende Lösung für ein problem, wenn es nicht erforderlich ist, dass subarray ist zusammenhängend. Habe ich falsch verstanden, die problem-Anweisung. Nicht löschen diese, wie jemand möglicherweise eine Idee, basierend auf der mine, die die Arbeit für das eigentliche problem.

Hier ist, was ich mir ausgedacht habe:

Erstellen Sie eine Instanz des dictionary (implementiert als hash-Tabelle, was O(1) in normalen Situationen). Die Schlüssel sind ganze zahlen, sind die Werte hash-sets der zahlen (auch O(1)) – var D = new Dictionary<int, HashSet<int>>.

Iteration durch das array A und für jede ganze Zahl n mit index i tun:

1. Prüfen Sie, ob Tasten n-1 und n+1 enthalten sind in D.
   • wenn keiner der Schlüssel vorhanden ist, tun D.Add(n, new HashSet<int>)
   • wenn nur ein Schlüssel vorhanden ist, z.B. n-1 tun D.Add(n, D[n-1])
   • wenn beide Tasten vorhanden sind, tun D[n-1].UnionWith(D[n+1]); D[n+1] = D[n] = D[n-1];
2. D[n].Add(n)

Gehen Sie nun durch die einzelnen Schlüssel in D und finden Sie die hash-set mit der größten Länge (Suche nach Länge O(1)). Die größte Länge wird die Antwort sein.

Meinem Verständnis, die schlimmsten Fall Komplexität O(n*log(n)), nur weil der UnionWith Betrieb. Ich weiß nicht, wie die Berechnung der durchschnittlichen Komplexität, aber es sollte in der Nähe der O(n). Bitte korrigieren Sie mich, wenn ich falsch bin.

UPD: Zu sprechen-code, hier ist eine test-Implementierung in C#, das gibt das richtige Ergebnis in den beiden OP ' s Beispiele:

var A = new int[] {4, 5, 1, 5, 7, 6, 8, 4, 1};
var D = new Dictionary<int, HashSet<int>>();

foreach(int n in A)
{
    if(D.ContainsKey(n-1) && D.ContainsKey(n+1))
    {
        D[n-1].UnionWith(D[n+1]);
        D[n+1] = D[n] = D[n-1];
    }
    else if(D.ContainsKey(n-1))
    {
        D[n] = D[n-1];
    }
    else if(D.ContainsKey(n+1))
    {
        D[n] = D[n+1];
    }
    else if(!D.ContainsKey(n))
    {
        D.Add(n, new HashSet<int>());
    }

    D[n].Add(n);
}

int result = int.MinValue;
foreach(HashSet<int> H in D.Values)
{
    if(H.Count > result)
    {
        result = H.Count;
    }
}

Console.WriteLine(result);

Nicht Ihre Hoffnungen, dies ist nur eine unvollständige Antwort.

Ich bin mir ziemlich sicher, dass das problem nicht lösbar in O(n). Leider kann ich nicht beweisen.

Wenn es gibt einen Weg, um es zu lösen in weniger als O(n^2) ist, würde ich vermuten, dass die Lösung basiert auf folgender Strategie:

1. Entscheiden, in O(n) (oder vielleicht O(n log n)), ob es existiert eine kontinuierliche subarray wie du es beschreibst mit mindestens i Elemente. Nennen wir dieses Prädikat E(i).
2. Verwenden Zweiteilung zu finden, die maximale i für die E(i) hält.

Die Gesamtlaufzeit dieses Algorithmus wäre dann O(n log n) (oder O(n log^2 n)).

Dies ist der einzige Weg, ich könnte kommen mit, um zu reduzieren das problem auf ein anderes problem, dass hat zumindest das potential, einfacher als die ursprüngliche Formulierung. Allerdings konnte ich nicht einen Weg finden, um zu berechnen E(i) in weniger als O(n^2), so kann ich Sie komplett ausschalten...

Hier sind 3 sinnvolle Lösungen:

Die erste ist O(nlog(n)) im Zeit-und O(n) Raum, das zweite ist O(n) im Zeit-und O(n) im Raum, und die Dritte ist O(n) im Zeit-und O(1) im Raum.

1. bauen binary search tree dann durchqueren es um.
   
   halten Sie 2 Zeiger, einen für den start von max Teilmenge und eine für das Ende.
   halten Sie die max_size Wert während der Iteration der Struktur.
   es ist ein O(n*log(n)) Zeit und Raum Komplexität.

2. kann man immer Sortieren, zahlen-set mit zählen, Sortieren in einer linearen Zeit
   und nach dem Durchlauf durch das array, was bedeutet, dass O(n) Zeit und Raum
   die Komplexität.

3. Vorausgesetzt, es ist nicht überlaufen oder einen großen ganzzahligen Datentyp. Vorausgesetzt das array ist ein mathematischer Satz (keine doppelten Werte). Sie können es in O(1) Speicher:

   • berechnen Sie die Summe der Reihe und dem Produkt aus dem array
   • herauszufinden, welche zahlen Sie haben es angenommen, Sie haben die min-und max-das original-set. Völlig es ist O(n) Zeit Komplexität.