====== Maximale Differenz in einer Zahlenmenge über die kumulative Summe finden ======
===== Motivation =====
Ein häufig auftretendes Problem ist es, die größte Differenz zwischen zwei beliebigen Elementen einer Menge zu finden. Bei großen Datenmengen ist es umso wichtiger, diese Operation so effizient wie möglich zu implementieren. Eine äußerst effiziente Methode bietet die Lösung des Problems über die kumulative Summe.

===== Definition =====
Als kumulierte Summe einer Zahlenfolge bezeichnet man die einfache Addition der einzelnen Zahlen. Dabei wird jede Zahl einfach zur vorhergehenden Summe addiert.\\ 
Wir können die Berechnung allgemein so darstellen: **s<sub>i</sub> = s<sub>i-1</sub> + x<sub>i</sub>**\\ 
Um diese Definition zu verdeutlichen, berechnen wir für zufällig gewählte Zahlen die kumulierten Summe:
^ Zahlen           | 3 |  7 | 12 |  4 | -6 |  2 | -4 |
^ Kumulierte Summe | 3 | 10 | 22 | 26 | 20 | 22 | 18 |
Noch einmal der Rechenvorgang aufgelistet:
^ Index (i) ^ Zahl (x) ^ Summe (s) ^ Berechnung ^
|         1 |        3 |         3 |      0 + 3 |
|         2 |        7 |        10 |      3 + 7 |
|         3 |       12 |        22 |    10 + 12 |
|         4 |        4 |        26 |     22 + 4 |
|         5 |       -6 |        20 |     26 - 6 |
|         6 |        2 |        22 |     20 + 2 |
|         7 |       -4 |        18 |     22 - 4 |
Jetzt wissen wir was die kumulative Summe ist und wie wir sie berechnen. Doch was kann man damit anstellen? Dazu sehen wir uns nun ein paar Beispiele an, die wir über diese Berechnung lösen bzw. optimieren können.


===== Beispiel: Optimierung von Aktienkäufen =====
==== Problemstellung ====
Um mit Aktien einen möglichst hohen Gewinn zu erzielen, muss der Verkaufspreis einen möglichst großen Unterschied (der natürlich positiv sein muss) zum Einkaufspreis aufweisen. Diese Aufgabe ist nicht so trivial wie sie anfangs vielleicht aussieht, denn die beste Lösung ist nicht immer der niedrigste (Einkauf) und der höchste Preis (Verkauf).\\ 
Wir nehmen an, dass wir Vorhersagen zu künftigen Aktienkursen haben und wollen den optimalen Einkaufs- und Verkaufszeitpunkt, sowie die jeweiligen Preise bestimmen.

==== Eingabe ====
Als Eingabe bekommen wir den Kurs einer Aktie in einem Zeitintervall. Dieses Intervall kann beliebig groß sein, aber je kleiner es ist, desto präziser wird die Berechnung.\\ 
Wir haben also folgende Eingabegrößen:
^ Variable             ^ Wert ^
| Anzahl an Kursen (n) |    8 |

Danach folgen n Kurse:
^ Index (i) ^   Kurs (k) ^
|         1 |         11 |
|         2 |         13 |
|         3 |          4 |
|         4 |          6 |
|         5 |         10 |
|         6 |          5 |
|         7 |         11 |
|         8 |          9 |

In unseren Test-Programmen werden die Eingabedaten von Funktionen geliefert. Diese müssen entsprechend dem Anwendungsfall angepasst werden. Im einfachsten Fall lesen diese Methoden von der Kommandozeile, die Daten können aber auch aus dem Netzwerk oder von einer Datenbank kommen.\\ 

Wie es für Aktienkurse üblich ist, können wir sie auch mit einem Diagramm darstellen:\\ 
{{:algo:stock.png?|}}

==== Quadratische Lösung ====
Eine Möglichkeit die maximale Differenz zu finden wäre die Berechnung aller Differenzen, aus denen man anschließend das Maximum auswählt.\\
<code c>
#include <stdio.h>
#include <limits.h>

// Maximum an eingegebenen Kurspositionen
const int maxN = 1000000;
// Maximaler Wert einer einzelnen Kursposition
const int maxV = 1000;

// Test-Daten
const int testData[] = { 11, 13, 4, 6, 10, 5, 11, 9 };
// Gibt das nächste Element in den Test-Daten zurück
int getNext()
{
  static int i = 0;
  return testData[i++];
}
// Gibt die Anzahl an Test-Daten zurück
int getCount()
{
  return sizeof( testData ) / sizeof( testData[0] );
}

int main()
{
  // Anzahl der Kurspositionen
  int n = getCount();
  // Zählvariablen für Schleifen
  int i, j;
  // Werte der einzelnen Kursposition
  int v[maxN];
  // Index des minimalen Wertes (optimaler Einkauf)
  int minIndex = -1;
  // Index des maximalen Wertes (optimaler Verkauf)
  int maxIndex = -1;

  // Kurse einlesen
  for( i = 0; i < n; i++ )
    v[i] = getNext();

  // Über alle Kurse iterieren
  for( i = 0; i < n; i++ )
  {
    // Differenz zu allen darauffolgenden Kursen bilden.
    // Ist das der erste Durchlauf (minIndex == -1) oder
    // die Differenz größer als das bisherige Maximum,
    // werden die bisherigen Indizes überschrieben.
    for( j = i + 1; j < n; j++ )
    {
      if( minIndex == -1 || v[j] - v[i] > v[maxIndex] - v[minIndex] )
      {
        maxIndex = j;
        minIndex = i;
      }
    }
  }
  
  // Ergebnis ausgeben
  if( minIndex != -1 )
    fprintf( stdout, "Minimum bei Zeiteinheit: %d; Minimaler Wert: %d\n"
                     "Maximum bei Zeiteinheit: %d; Maximaler Wert: %d\n"
                     "Gewinn: %d\n", 
             minIndex + 1, v[minIndex],
             maxIndex + 1, v[maxIndex],
             v[maxIndex] - v[minIndex] );

  return 0;
}
</code>
Ausgabe:
  Minimum bei Zeiteinheit: 3; Minimaler Wert: 4
  Maximum bei Zeiteinheit: 7; Maximaler Wert: 11
  Gewinn: 7
Die optimale Strategie im angegebenen Zeitintervall ist also im 3. Zeitintervall zu kaufen und im 7. zu verkaufen. Dabei erhalten wir einen Gewinn von 7 pro Aktie.\\ 
Da wir für jede Kursposition die Differenz zu allen darauffolgenden ausrechnen, ergibt sich ein quadratischer Aufwand. In Kurzschreibweise bedeutet das: **O(n<sup>2</sup>)**

==== Lineare Lösung: Kumulative Summe ====
Die obrige Lösung funktioniert in unserem Beispiel ganz gut. Aber was ist, wenn wir nicht 8 sondern ein paar Millionen Kurspositionen haben? Versuchen wir eine bessere Lösung mit der kumulativen Summe zu finden.\\ 
Gehen wir von der ersten Kursposition aus und addieren alle Kursdifferenzen dazu, erhalten wir logischerweise immer den aktuellen Kurs. Wenn wir uns jetzt das Minimum merken und immer die Differenz zum aktuellen Kurs bilden, können wir in linearem Aufwand das gesuchte Ergebnis finden.
<code c>
#include <stdio.h>
#include <limits.h>

// Test-Daten
const int testData[] = { 11, 13, 4, 6, 10, 5, 11, 9 };
// Gibt das nächste Element in den Test-Daten zurück
int getNext()
{
  static int i = 0;
  return testData[i++];
}
// Gibt die Anzahl an Test-Daten zurück
int getCount()
{
  return sizeof( testData ) / sizeof( testData[0] );
}

int main()
{
  // Anzahl der Kurspositionen
  int n = getCount();
  // Index des minimalen Wertes (optimaler Einkauf)
  int minIndex = 0;
  // Index des maximalen Wertes (optimaler Verkauf)
  int maxIndex = -1;
  // Minimaler Wert (Einkaufspreis)
  int min;
  // Maximale Kursdifferenz (Verkaufspreis)
  int maxDiff = INT_MIN;
  // Aktuelle Summe aller Kursänderungen. Dadurch enthält
  // diese Variable auch immer den aktuellen Kurs.
  long sum;
  // Aktueller Aktienkurs
  int currentPrice;
  // Vorheriger Aktienkurs
  int oldPrice;

  // 1. Kurs einlesen und als bisherige Summe festlegen.
  currentPrice = getNext();
  sum = min = oldPrice = currentPrice;
  // Alle Aktienkurse einlesen und Ergebnis berechnen
  int i;
  for( i = 1; i < n; i++ )
  {
    // Aktuellen Kurs einlesen
    currentPrice = getNext();
    // Wir summieren die Kursänderungen auf.
    sum += currentPrice - oldPrice;
    // Ist der Kurs kleiner als das bisherige Minimum, wird 
    // die aktuelle Kursposition als neues Minimum gespeichert.
    if( sum < min )
    {
      min = sum;
      minIndex = i;
    }
    // Ist der Kursunterschied zwischen dem bisherigen minimalen und
    // dem aktuellen Kurs größer als das bisherige Maximum, wird
    // die aktuelle Kursposition als neues Maximum gespeichert.
    if( sum - min > maxDiff )
    {
      maxDiff = sum - min;
      maxIndex = i;
    }
    // Wir speichern den aktuellen Kurs für den nächsten Durchlauf als
    // alten Kurs.
    oldPrice = currentPrice;
  }

  // Ergebnis ausgeben.
  fprintf( stdout, "Minimum bei Zeiteinheit: %d; Minimaler Wert: %d\n"
                   "Maximum bei Zeiteinheit: %d; Maximaler Wert: %d\n"
                   "Gewinn: %d\n", 
           minIndex + 1, min, 
           maxIndex + 1, maxDiff + min, 
           maxDiff );

  return 0;
}
</code>
Ausgabe:
  Minimum bei Zeiteinheit: 3; Minimaler Wert: 4
  Maximum bei Zeiteinheit: 7; Maximaler Wert: 11
  Gewinn: 7
In dieser Version haben wir nicht nur den rechnerischen Aufwand von O(n<sup>2</sup>) auf **O(n)** verringert, wir ersparen uns sogar ein Array mit den gesamten Daten.


===== Beispiel: Größtmöglicher Hausplatz =====
==== Problemstellung ====
Wir haben ein quadratisches Grundstück, auf das wir ein Haus bauen möchten. Dieses Grundstück ist jetzt aber keine komplett leere Fläche, sondern beinhaltet auch Hindernisse wie zum Beispiel Bäume. Da wir diese nur ungern fällen möchten, suchen wir eine möglichst große rechteckige Teilfläche, auf der wir unser Haus platzieren können, ohne ein Hindernis zu entfernen.

==== Eingabe ====
Zuerst bekommen wir die Seitenlänge der quadratischen Fläche als Eingabe:
^ Variable        ^ Wert ^
| Seitenlänge (s) | 7    |
Danach folgt die Anzahl der Hindernisse, die sich auf der Fläche befinden:
^ Variable                   ^ Wert ^
| Anzahl der Hindernisse (n) | 5    |
Im Anschluss folgen noch die Koordinaten der Hindernisse (Koordinaten: 1 <= x, y <= s):
^ x-Koordinate ^ y-Koordinate ^
| 2            | 3            |
| 4            | 2            |
| 4            | 6            |
| 7            | 8            |
| 7            | 4            |
Zeichnen wir uns diese Matrix auf, erhalten wir folgendes Ergebnis:\\ 
{{:algo:area.png|}}
\\ 
In der Grafik steht die Farbe Grün für freie Felder und Schwarz für belegte Felder. Wir suchen nun den größten rechteckigen Block aus grünen Feldern. Dabei interessieren uns natürlich Koordinaten und Breite bzw. Höhe des Rechtecks.

==== n^6 Lösung ====
Ein relativ einfaches, aber sehr aufwendiges Verfahren ist es, alle möglichen Felder durchzuprobieren. Dabei geht man alle einzelnen Koordinaten durch und sucht für alle davon ausgehenden Breiten und Höhen das größte freie Feld. Eine Implementierung könnte so aussehen:
<code c>
#include <stdio.h>

char area[1001][1001];

// Test-Daten
const char testData[] = { 7, 5,    // s, n
                          3, 2,    // y1, x1
                          2, 4,    // y2, x2
                          6, 4,    // y3, x3
                          4, 6,    // y4, x4
                          7, 6 };  // y5, x5
// Gibt das nächste Element in den Test-Daten zurück
int getNext()
{
  static int i = 0;
  return testData[i++];
}

int main( int argc, char *argv[] )
{
  // Größe des Quadrates abfragen
  int s = getNext();
  // Anzahl an Hindernissen abfragen
  int n = getNext();
  // Noch keine passende Fläche gefunden, deshalb mit -1 vorbelegt
  int x = -1, y = -1, maxW = -1, maxH = -1;
  // Schleifenzähler
  int i, j, k, l, a, b;
  // Gibt an, ob ein Block frei von Hindernissen ist
  int isFree;
  // Hindernisse einlesen und im Array kennzeichnen
  for( i = 0; i < n; i++ )
    area[getNext()][getNext()] = 1;
  // Durch alle Zeilen iterieren (y-Koordinate)
  for( j = 1; j <= s; j++ )
  {
    // Durch alle Spalten iterieren (x-Koordinate)
    for( i = 1; i <= s; i++ )
    {
      // Alle möglichen Breiten versuchen, beginnend bei der größten
      for( k = s; k >= i; k-- )
      {
        // Alle möglichen Höhen versuchen, beginnend bei der größten
        for( l = s; l >= j; l-- )
        {
          // Prüfen, ob das Feld leer ist
          isFree = 1;
          for( a = i; a <= k && isFree; a++ )
          {
            for( b = j; b <= l && isFree; b++ )
            {
              if( area[b][a] )
                isFree = 0;
            }
          }
          // Feld ist leer
          if( isFree )
          {
            // Prüfen, ob das neue Feld größer ist als das bisher
            // größte gefundene. Gegebenenfalls Koordinaten und
            // Größe speichern
            int newW = k - i + 1;
            int newH = l - j + 1;
            if( x == -1 || ( maxW * maxH ) < ( newW * newH ) )
            {
              x = i;
              y = j;
              maxW = newW;
              maxH = newH;
            }
          }
        }
      }
    }
  }
  // Ergebnis ausgeben
  fprintf( stdout, "x: %d y: %d w: %d h: %d\n", x, y, maxW, maxH );
  return 0;
}
</code>
Ausgabe:
  x: 1 y: 4 w: 3 h: 4
Wir bekommen also folgende gelb markierte Fläche als Ergebnis:\\ 
{{:algo:freearea.png|}} \\ 
Das Ergebnis sieht schon mal sehr gut aus. Aber am Code sofort fällt die Verschachtelung von 6 Schleifen auf. Wir haben hier also einen Algorithmus der Ordnung **O(n<sup>6</sup>)**, der sehr schnell anwächst.\\ 
\\ 
Hinweis: In der Implementierung wurde der Index 0 im Array vernachlässigt. Das verschwendet zwar Speicher, hat aber einen Grund, den wir im nächsten Abschnitt näher betrachten werden.

==== Lösung: Kumulative Summe ====
So können wir unser Programm aber nicht einfach stehen lassen. Es liefert zwar die richtige Lösung, die Berechnung ist aber sehr aufwendig.

\\
\\
FIXME skizzen, erklärung

===== Siehe auch =====
  * [[struct:tree:fenwick|Binary Indexed Tree (Fenwick Tree)]]