Dynamische Optimierung, Beispiel II

(eine Aufgabe aus Jon Bentley: Programming Pearls)

• Eingabe: Zahlenfolge [x₁, x₂,..., x_n],
• Ausgabe: Indizes (a, b), für die x_a + x_a+1 +...+ x_b maximal

naiver Algorithmus:

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);
    }
}

Laufzeit? Geht besser?

...ja, mit passenden Invarianten:

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

wer sagt ,,das war ja leicht,``

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

• gegeben eine Matrix x[1..m][1..n],
• gesucht eine Untermatrix x[a..b][c..d] mit maximaler Elementsumme