Class Loesung41

java.lang.Object
  Loesung41

public class Loesung41
extends Object

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

Version:

$Revision: 1.2 $

Author:

Arne Johannessen

See Also:

Aufgabenblatt 4

Constructor Summary

Loesung41()

Method Summary

static int	findMaximumSum(int[] array) Loest das Maximum-Sub-Array--Problem fuer den uebergebenen Array im Divide-and-Conquer--Verfahren.
protected static int	findMaximumSum(int[] array, int leftIndex, int rightIndex) 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

Loesung41

public Loesung41()

Method Detail

findMaximumSum

public static 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

protected static 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

main

public static void main(String[] args)

Treiber fuer Aufruf von der Kommandozeilenschnittstelle.