Problem 18: Maximale Summe eines Pfades I

Gesucht ist die maximale Summe eines Pfades durch ein Dreieck von Zahlen! [ das englische Original ]

Als Pfad wird hier ein Weg bezeichnet, der immer an der Spitze des Dreiecks beginnt und sich dann über die jeweils benachbarten Zellen der darunter liegenden Zeilen fortsetzt. Da nicht der Pfad, sondern dessen Summe gesucht wird und dabei dann auch nur die größte Summe interessant ist, ist hier ein iterativer Algorithmus leicht gefunden:

Algorithmus zur zeilenweisen Berechnung des maximalen Pfades durch ein gegebenes Dreieck von Zahlen
Algorithmus zur zeilenweisen Berechnung des maximalen Pfades durch ein gegebenes Dreieck von Zahlen

Wie man in der Grafik sehen kann, werden einfach alle Elemente der nachfolgenden Zeile mit den benachbarten Elementen der Vorgängerzeile addiert. Hat ein Element 2 benachbarte Vorgänger wird immer nur das größere von beiden (grüne Zellen) gewählt. Als Ergebnis erhält man eine neue Zeile (gelbe Zellen) mit genau derselben Anzahl von Elementen, wie die gegebene Nachfolgerzeile. Damit kann man dann den nächsten Schritt der Iteration gehen.

Die Berechnung der maximalen Summe von 2 Zeilen habe ich in eine eigene Methode ausgelagert:

protected Integer[] sumTriangleRows( Integer[] row1, Integer[] row2 ) {
   int len = row2.length;
   Integer[] result = new Integer[ len ];

   result[ 0 ] = row1[ 0 ] + row2[ 0 ];

   for( int i=1; i<len-1; i++ )
      result[ i ] = row2[ i ] + ( ( row1[ i-1 ] > row1[ i ] ) ? row1[ i-1 ] : row1[ i ] );

   result[ len-1 ] = row1[ len-2 ] + row2[ len-1 ];

   return result;
}

Wie man sieht, habe ich diese Methode für erbende Klassen verfügbar gemacht. Da Problem 67 auf demselben Algorithmus basiert, kann man hier sehr gut nachnutzen!

Die Iteration selbst stellt sich dann recht trivial dar:

@Override
public String solve() {

   Integer[] cur = sumTriangleRows( data.get( 0 ), data.get( 1 ) );
   for( int i=2; i<data.size(); i++ )
      cur = sumTriangleRows( cur, data.get( i ) );

   Arrays.sort( cur );

   return IO.i2s( cur[ cur.length-1 ] );
}

Den vollständigen Quellcode der Klasse für die Lösung des Problems 18 kann man sich hier anschauen!

<< Problem 17 Übersicht Problem 19 >>

Kommentar verfassen

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: