\documentclass{bschlangaul-aufgabe}
\bLadePakete{java}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 4},
  Thematik = {maximale Teilsumme},
  Referenz = 66115-2012-H.T1-A4,
  RelativerPfad = Examen/66115/2012/09/Thema-1/Aufgabe-4.tex,
  ZitatSchluessel = examen:66115:2012:09,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Teile-und-Herrsche (Divide-and-Conquer)},
  EinzelpruefungsNr = 66115,
  Jahr = 2012,
  Monat = 09,
  ThemaNr = 1,
  AufgabeNr = 4,
}

Gegeben ist ein Array $a$ von ganzen Zahlen der Länge $n$, \zB:
\index{Teile-und-Herrsche (Divide-and-Conquer)}
\footcite{examen:66115:2012:09}

\begin{center}
\begin{tabular}{l|llllllllll}
$i$  & 0  & 1  & 2 & 3 & 4  & 5 & 6  & 7  & 8 & 9\\\hline
$a_i$ & 5 & -6 & 4 & 2 & -5 & 7 & -2 & -7 & 3 & 5\\
\end{tabular}
\end{center}

\noindent
Im Beispiel ist also $n = 10$. Es soll die maximale Teilsumme berechnet
werden, also der Wert des Ausdrucks

\begin{displaymath}
\max_{i,j \leq n} \sum^{j-1}_{k=1} a_k
\end{displaymath}

\noindent
Im Beispiel ist dieser Wert $8$ und wird für $i = 8$,$j = 10$ erreicht.
Entwerfen Sie ein Divide-And-Conquer Verfahren, welches diese
Aufgabenstellung in Zeit $\mathcal{O}(n \log n)$ löst. Skizzieren Sie
Ihre Lösung hinreichend detailliert.

Tipp: Sie sollten ein geringfügig allgemeineres Problem lösen, welches
neben der maximalen Teilsumme auch noch die beiden „maximalen
Randsummen” berechnet. Die werden dann bei der Endausgabe verworfen.

\bJavaExamen{66115}{2012}{09}{Teilsumme}

\end{document}