Class Loesung81

java.lang.Object
  Loesung81

 class Loesung81
extends Object

Loesungsvorschlag fuer Aufgabe 8-1: Maximum-Sub-Array: Divide-and-Conquer--Loesung mit O(n*log(n)).

Version:

$Revision: 1.1 $

Author:

Arne Johannessen

See Also:

Aufgabenblatt 8

Constructor Summary

Loesung81()

Method Summary

(package private) int	findMaximumSum(int[] array) Loest das Maximum-Sub-Array--Problem fuer den uebergebenen Array im Divide-and-Conquer--Verfahren.
(package private) int	findMaximumSum(int[] array, int leftIndex, int rightIndex) Loest das Maximum-Sub-Array--Problem fuer den uebergebenen Sub-Array im Divide-and-Conquer--Verfahren.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Loesung81

Loesung81()

Method Detail

findMaximumSum

int findMaximumSum(int[] array)

Loest das Maximum-Sub-Array--Problem fuer den uebergebenen Array im Divide-and-Conquer--Verfahren.

Parameters:

array - der fuer die Bestimmung der Problemloesung heranzuziehende Gesamt-Array

Returns:

die maximale Teilsumme von array

Throws:

NullPointerException - falls array == null

See Also:

findMaximumSum(int[],int,int)

findMaximumSum

int findMaximumSum(int[] array,
                   int leftIndex,
                   int rightIndex)

Loest das Maximum-Sub-Array--Problem fuer den uebergebenen Sub-Array im Divide-and-Conquer--Verfahren.

Der Sub-Array wird in zwei etwa gleich grosse Teile gesplittet, fuer die jeweils das Problem rekursiv geloest wird. Zusaetzlich wird diejenige maximale Teilsumme ermittelt, welche die Trennstelle ueberbrueckt. Diejenige dieser drei Teilsummen, die am hoechsten ist, wird zurueckgeliefert.

Dieser Divide-and-Conquer--Algorithmus laesst sich als easy-split, hard-join charakterisieren.

Parameters:

array - der fuer die Bestimmung der Problemloesung heranzuziehende Gesamt-Array

leftIndex - die linke Begrenzung des Sub-Arrays, fuer den die maximale Teilsumme ermittelt werden soll

rightIndex - die rechte Begrenzung des Sub-Arrays, fuer den die maximale Teilsumme ermittelt werden soll

Returns:

die maximale Teilsumme im durch die Parameter definierten Sub-Array

Throws:

NullPointerException - falls array == null

ArrayIndexOutOfBoundsException - falls die beiden Indizes keine gueltigen und sinnvollen Array-Indizes sind