Dynamische Optimierung, Beispiel II

(eine Aufgabe aus Jon Bentley: Programming Pearls)

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:



Johannes Waldmann 2007-06-13