Coder Forum

Java Quellcode

/**
 * Algorithmen und Datenstrukturen<br>
 * FH-Wiesbaden, Sommersemester 2006<br>
 * Uebung04/Aufgabe02 - Rekursive Berechnung eines maximalen sub.Arrays<br>
 * 
 * @author Sebastian Schmitt
 * @version 1.0 
 */
package Aufgabe02;
import fhw.*;
 
 
public class MaxSubArrayRekursiv {
 
	/**
	 * @param args Kommandozeilenparameter
	 */
	public static void main(String[] args) {
		ADSTool.resetTime();
 
		int a[];
		a=ADSTool.readIntArray("u4a1.dat");
 
		int ergebniss=maxSubRec(a);
		System.out.println(ergebniss);//46610
 
		System.out.print("Zeit: "+ADSTool.stringRTime());//0.03s !!!
	}
	/**
	 * errechnet die maximale linke Randsumme eines int[]
	 * @param a int[]
	 * @return maximale linke Randsumme von a[]
	 */
	static int maxSumLeft(int [] a){
		int max=0;
		int tmp=0;
		for(int i=0; i<a.length; i++){
			tmp+=a[i];
			if(tmp>max)
				max=tmp;
		}
		return max;
	}
	/**
	 * errechnet die maximale rechte Randsumme eines int[]
	 * @param a int[]
	 * @return maximale rechte Randsumme von a[]
	 */
	static int maxSumRight(int a[]){
		int max=0;
		int tmp=0;
		for(int i=a.length-1; i>0; i--){
			tmp+=a[i];
			if(tmp>max)
				max=tmp;
		}
		return max;
	}
	/**
	 * errechnet das maximale sub-Array eines int[]
	 * @param a int[]
	 * @return maximales sub-array von a[]
	 */
	static int maxSubRec(int[] a){
		if(a.length==1)
			return a[0]>0 ? a[0] : 0;
			else{
				int[] b=new int[a.length/2];
				System.arraycopy(a,0,b,0,a.length/2);//linke Haelfte von a[]
				int[] c=new int[a.length-a.length/2];
				System.arraycopy(a,a.length/2,c,0,a.length-a.length/2);//rechte Haelfte von a[]
 
				int maxa=0;
				maxa=maxSumRight(b)+maxSumLeft(c);//linke + rechte Randsumme
				int maxb=maxSubRec(b);//"eine Stufe Tiefer" in die linke H. von a[]
				int maxc=maxSubRec(c);//"eune Stufe Tiefer" in die rechte H. von a[]
 
				//return Maximum(maxa/maxb/maxc) fuer uebergeordete Rekursionen
				if(maxa>=maxb && maxa>=maxc)
					return maxa;
				else if(maxb>=maxa && maxb>=maxc)
					return maxa;
				else
					return maxc;
			}
	}
}

Java Quellcode

package aufgabe2;
import fhw.*;
 
/** 
 * FH Wiesbaden, FB 06, Medieninformatik, Algorithmen und Datenstrukturen, SS 2006<br>
 * Uebungsblatt 4, Aufgabe 2<br><br>
 * 
 * Programm, das rekursiv die maximale Teilsumme eines Arrays mit n ganzen Zahlen findet
 * und die Summe, sowie die Indizes der Teilfolge ausgibt<br>
 * Eingabe: <br>
 * Ausgabe: <br><br>
 *
 * Getestet mit Microsoft Windows XP Media Center Edition, Java-Version 1.5.0_05<br>
 *
 * @author Phibee
 * @version 1.0 (28.04.2006)
 */
 
public class MaxSubArrayRekArray {
 
	/**
	 * Startroutine des Programms
	 * @param args Kommandozeilenparameter
	 */
 
	public static void main(String[] args) {
 
		int[] a = ADSTool.readIntArray("u4a1simple.dat");
 
		int[] max = {0,0,0};
		max[0] = getMaxSubArray(a, 0, a.length-1)[0];
		max[1] = getMaxSubArray(a, 0, a.length-1)[1];
		max[2] = getMaxSubArray(a, 0, a.length-1)[2];
 
		System.out.println("Teilfolge von "+max[0]+" bis "+max[1]+" maximal mit Wert: "+max[2]);
 
	} // Ende main
 
	/**
	 * Methode, die rekursiv die maximale Teilsumme eines Arrays mit n ganzen Zahlen findet
	 * @param a Array
	 * @param start Startindex
	 * @param ende Endindex
	 * @return Array mit groesster Teilsumme und deren Indizes
	 */
	public static int[] getMaxSubArray(int[] a, int start, int ende) {
		int[] max = {0,0,0};
		if (start==ende) {
			if (a[start]>0) {
				max[0]=start;
				max[1]=ende;
				max[2]=a[start];
			}
			else {
				max[0]=start;
				max[1]=ende;
				max[2]=0;
			}
			return max;
		}
		else {
			int[] schnittstelle = new int[3];
			schnittstelle[0]=rechteRandsumme(a,start,(start+ende)/2)[0];
			schnittstelle[1]=linkeRandsumme(a,(start+ende)/2+1,ende)[1];
			schnittstelle[2]=rechteRandsumme(a,start,(start+ende)/2)[2]+
			linkeRandsumme(a,(start+ende)/2+1,ende)[2];
			return (max((getMaxSubArray(a,start,(start+ende)/2)),
					schnittstelle,
					getMaxSubArray(a,(start+ende)/2+1,ende)));
		}
 
	} // Ende getMaxSubArray
 
	/**
	 * Methode zur Bestimmung der groessten dreier Teilsummen
	 * @param a groesste Teilsumme der linken Haelfte
	 * @param b Summe der groessten linken Randsumme der rechten Haelfte
	 * und der groessten rechten Randsumme der linken Haelfte
	 * @param c groesste Teilsumme der rechten Haelfte
	 * @return Array mit groesster der 3 Teilsummen und deren Indizes
	 */
	public static int[] max(int[] a, int[] b, int[] c) {
		int[] max={0,0,0};
		if (a[2]>b[2]) {
			if (a[2]>c[2]) max=a;			
		}
		else if (b[2]>c[2]){
			max=b;
		}
		else max=c;
		return max;
	}
 
	/**
	 * linke Randsumme des rechten Teilarrays
	 * @param a Array
	 * @param start Startindex
	 * @param ende Endindex
	 * @return Array mit groesster Randsumme und deren Indizes
	 */
	public static int[] linkeRandsumme(int[] a, int start, int ende) {
		int sum=0;
		int[] max={start,start,0};
		for (int i=start ; i<=ende ; i++) {
			sum+=a[i];
			if (sum>max[2]) {
				max[0]=start;
				max[1]=i;
				max[2]=sum;
			}
		}
		return max;
	}
 
	/**
	 * rechte Randsumme des linken Teilarrays
	 * @param a Array
	 * @param start Anfangsindex
	 * @param ende Endindex
	 * @return Array mit groesster Randsumme und deren Indizes
	 */
	public static int[] rechteRandsumme(int[] a, int start, int ende) {
		int sum=0;
		int[] max={ende,ende,0};
		for (int i=ende ; i>=start ; i--) {
			sum+=a[i];
			if (sum>max[2]) {
				max[0]=i;
				max[1]=ende;
				max[2]=sum;
			}
		}
		return max;
	}
 
} // Ende MaxSubArrayRek