\begin{slide}{Dynamische Optimierung, Beispiel II}

(eine Aufgabe aus Jon Bentley: Programming Pearls)

\begin{itemize}
\item
  Eingabe:  Zahlenfolge $[x_1, x_2, \ldots, x_n]$,
\item
  Ausgabe: Indizes $(a,b)$, für die
  $x_a + x_{a+1} + \ldots + x_b$ maximal
\end{itemize}

\newpage

naiver Algorithmus:
\begin{verbatim}
int best = 0;
for (a=1; a<n; a++) {
    for (b=a; b<n; b++) {
        int sum = 0;
        for (int i=a; i<= b; i++) {    
            sum += x[i];
        }
        best = max(best,sum);
    }
}
\end{verbatim}
Laufzeit? Geht besser?

\newpage

\dots ja, mit passenden Invarianten:

\begin{verbatim}
int best_so_far
int best_ending_here
for (int i=1; i<n; i++) {
    // INVARIANT:
    // best_so_far ist ...
    // best_ending_here ist ...
}
\end{verbatim}

\newpage

wer sagt \glqq das war ja leicht,\grqq\

der finde bitte einen effizienten Algorithmus
für die entsprechende zweidimensionale Aufgabe:

\begin{itemize}
\item 
  gegeben eine Matrix $x[1..m][1..n]$, 
\item
  gesucht eine Untermatrix $x[a..b][c..d]$
  mit maximaler Elementsumme
\end{itemize}


\end{slide}

