Endlich....es ist vollbracht !!!!!!!!!!!!!!!!!!!!!!!!!!!!
1000 Dank an Stefan & Marco :shock:
Alles anzeigen
1000 Dank an Stefan & Marco :shock:
Quellcode
- package ueb4;
- import fhw.ADSTool;
- public class A2 {
- /**
- * @param args
- */
- public static void main(String[] args) {
- // int[] a = ADSTool.readIntArray(args.length==0 ? "u4a1.dat" :
- // args[0]);
- int summe = 0, max = 0;
- int[] a = { 31, -41, 59, 26, -53 };
- // maxsub();
- System.out.println("Größte Teilsumme:"
- + maxSubArray(a, 0, a.length - 1));
- }
- private static int maxSubArray(int[] a, int startpos, int endpos) {
- int mitte = (startpos + endpos) / 2;
- if (startpos == endpos) {
- if (a[startpos] > 0)
- return a[startpos];
- else
- return 0;
- } else {
- int lRand = RechteRandsumme(a, startpos, mitte);
- int rRand = LinkeRandsumme(a, mitte + 1, endpos);
- int sumRaender = lRand + rRand;
- int lhaelfte = maxSubArray(a, startpos, mitte);
- int rhaelfte = maxSubArray(a, mitte + 1, endpos);
- System.out.println("Startposition:" + startpos + " Mitte: " + mitte
- + " Endposition: " + endpos);
- System.out.println("Linke Hälfte: " + lhaelfte);
- System.out.println("Rechte Hälfte: " + rhaelfte);
- System.out.println("LinkeRandsumme:" + lRand
- + " + RechteRandsumme: " + rRand + " = " + sumRaender);
- return max(lhaelfte, rhaelfte, lRand + rRand);
- }
- }
- private static int RechteRandsumme(int a[], int start, int ende) {
- int max = 0;
- int sum = 0;
- for (int i = ende; i >= start; i--) {
- sum += a[i];
- if (sum > max) {
- max = sum;
- }
- }
- return max;
- }
- private static int LinkeRandsumme(int a[], int start, int ende) {
- int max = 0;
- int sum = 0;
- for (int i = start; i <= ende; i++) {
- sum += a[i];
- if (sum > max) {
- max = sum;
- }
- }
- return max;
- }
- private static int max(int a, int b, int c) {
- int max0 = (a > b) ? a : b;
- int max = (max0 > c) ? max0 : c;
- return max;
- }
- }