Class Loesung42

java.lang.Object
  Loesung42

All Implemented Interfaces:

MaximumSubArraySolver

public class Loesung42
extends Object
implements MaximumSubArraySolver

Loesungsvorschlag fuer Aufgabe 4-2. Divide-and-Conquer--Loesung fuer das Maximum-Sub-Array--Problem mit O(n*log(n))-Komplexitaet.

Version:

$Revision: 1.1 $

Author:

Arne Johannessen

See Also:

Aufgabenblatt 4

Constructor Summary

Loesung42()

Method Summary

SubArray	findMaximumSubArray(int[] array) Loest das Maximum-Sub-Array--Problem fuer den uebergebenen Array im Divide-and-Conquer--Verfahren.
protected SubArray	findMaximumSubArray(SubArray array) Loest das Maximum-Sub-Array--Problem fuer den uebergebenen Sub-Array im Divide-and-Conquer--Verfahren.
static void	main(String[] args) Treiber fuer Aufruf von der Kommandozeilenschnittstelle.

Methods inherited from class java.lang.Object

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

Constructor Detail

Loesung42

public Loesung42()

Method Detail

findMaximumSubArray

public SubArray findMaximumSubArray(int[] array)

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

Specified by:

findMaximumSubArray in interface MaximumSubArraySolver

Parameters:

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

Returns:

eine neu erstellte Instanz der Klasse SubArray, deren Gesamt-Array identisch mit dem dieser Methode uebergebenen array ist und deren Sub-Array--Definition derart ist, dass sie eine korrekte Loesung des Maximum-Sub-Array--Problems darstellt.

Throws:

NullPointerException - falls array == null

See Also:

findMaximumSubArray(SubArray)

findMaximumSubArray

protected SubArray findMaximumSubArray(SubArray array)

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 der Maximum-Sub-Array ermittelt, innerhalb dessen Grenzen sich die Trennstelle befindet. Derjenige dieser drei Sub-Arrays, dessen Summe der Elemente 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

Returns:

eine neu erstellte Instanz der Klasse SubArray, deren Gesamt-Array identisch mit dem des dieser Methode uebergebenen array ist und deren Sub-Array--Definition derart ist, dass sie eine korrekte Loesung des Maximum-Sub-Array--Problems darstellt.

Throws:

NullPointerException - falls array == null

main

public static void main(String[] args)

Treiber fuer Aufruf von der Kommandozeilenschnittstelle.