algorithm
Maximaler Subarray-Algorithmus

Informationen zum maximalen Teilarray-Algorithmus

Ein maximales Subarray-Problem ist die Methode, um das zusammenhängende Subarray innerhalb eines eindimensionalen Zahlenfeldes zu finden, das die größte Summe hat.

Das Problem wurde ursprünglich von Ulf Grenander von der Brown University 1977 als vereinfachtes Modell für die Abschätzung der maximalen Wahrscheinlichkeit von Mustern in digitalisierten Bildern vorgeschlagen.

Wir können das Problem so lösen, lassen Sie uns eine Liste verschiedener Ganzzahlen betrachten. Wir könnten daran interessiert sein, welche vollständig benachbarte Teilmenge die größte Summe haben wird. Wenn wir beispielsweise das Feld [0, 1, 2, -2, 3, 2] , ist das maximale Unterfeld [3, 2] mit einer Summe von 5 .

Brute-Force-Ansatz für die Lösung:

Diese Methode ist am ineffizientesten, um die Lösung herauszufinden. In diesem Fall werden wir jedes einzelne mögliche Subarray durchgehen und dann die Summe aller finden. Vergleichen Sie zum Schluss alle Werte und ermitteln Sie das maximale Subarray.

Pseudo-Code für den Brute-Force-Ansatz:

MaxSubarray(array)
  maximum = 0
  for i in input
    current = 0
    for j in input
       current += array[j]
       if current > maximum
         maximum = current
  return maximum

Die zeitliche Komplexität für die Brute-Force-Methode ist O(n^2) . Also lasst uns den Ansatz teilen und überwinden.

Lösungsansatz teilen und erobern:

Finden Sie die Summe der Subarrays auf der linken Seite, die Subarrays auf der rechten Seite. Dann werfen Sie einen Blick durch alle, die die mittlere Kluft überqueren, und geben Sie schließlich die maximale Summe zurück. Da dies ein Divide-and-Conquer-Algorithmus ist, müssen wir zwei verschiedene Funktionen haben.

Der erste Schritt ist der Teilungsschritt.

maxSubarray(array)
  if start = end
    return array[start]
  else
    middle = (start + end) / 2
    return max(maxSubarray(array(From start to middle)), maxSubarray(array(From middle + 1 to end)), maxCrossover(array))

Trennen Sie im zweiten Teil die verschiedenen Teile, die im ersten Teil erstellt werden.

maxCrossover(array)
  currentLeftSum = 0
      leftSum = 0
  currentRightSum = 0
      rightSum = 0
  for i in array
    currentLeftSum += array[i]
    if currentLeftSum > leftSum
      leftSum = currentLeftSum
  for i in array
    currentRightSum += array[i]
    if currentRightSum > rightSum
      rightSum = currentRightSum
  return leftSum + rightSum

Die O(nlogn) Komplexität für die Divide and Conquer-Methode ist O(nlogn) . Kommen wir zu einem dynamischen Programmieransatz.

Dynamischer Programmieransatz:

Diese Lösung wird auch als Kadanes Algorithmus bezeichnet. Es ist ein linearer Zeitalgorithmus. Diese Lösung wird von Joseph B. Kadane Ende der 70er Jahre gegeben.

Dieser Algorithmus durchläuft gerade die Schleife und ändert kontinuierlich die aktuelle maximale Summe. Interessanterweise ist dies ein sehr einfaches Beispiel für einen dynamischen Programmieralgorithmus, da ein überlappendes Problem auftritt und es reduziert wird, um eine effizientere Lösung zu finden.

Pseudocode des Kadane-Algorithmus:

MaxSubArray(array)
  max = 0
  currentMax = 0
  for i in array
    currentMax += array[i]
    if currentMax < 0
      currentMax = 0
    if max < currentMax
      max = currentMax
  return max

Die zeitliche Komplexität für den Kadane-Algorithmus ist O(n) .

C # -Implementierung

public class MaximumSubarray
{
    private static int Max(int a, int b)
    {
        return a > b ? a : b;
    }

    static int MaxSubArray(int[] input, int n)
    {
        int max = input[0];
        int currentMax = input[0];
        for (int i = 1; i < n; i++)
        {
            currentMax = Max(input[i], currentMax + input[i]);
            max = Max(max, currentMax);
        }
        return max;
    }

    public static int Main(int[] input)
    {
        int n = input.Length;
        return MaxSubArray(input, n);
    }
}