Maximum Sub Array Problem: Rekursiv

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Maximum Sub Array Problem: Rekursiv

    Endlich....es ist vollbracht !!!!!!!!!!!!!!!!!!!!!!!!!!!!

    1000 Dank an Stefan & Marco :shock:


    Quellcode

    1. package ueb4;
    2. import fhw.ADSTool;
    3. public class A2 {
    4. /**
    5. * @param args
    6. */
    7. public static void main(String[] args) {
    8. // int[] a = ADSTool.readIntArray(args.length==0 ? "u4a1.dat" :
    9. // args[0]);
    10. int summe = 0, max = 0;
    11. int[] a = { 31, -41, 59, 26, -53 };
    12. // maxsub();
    13. System.out.println("Größte Teilsumme:"
    14. + maxSubArray(a, 0, a.length - 1));
    15. }
    16. private static int maxSubArray(int[] a, int startpos, int endpos) {
    17. int mitte = (startpos + endpos) / 2;
    18. if (startpos == endpos) {
    19. if (a[startpos] > 0)
    20. return a[startpos];
    21. else
    22. return 0;
    23. } else {
    24. int lRand = RechteRandsumme(a, startpos, mitte);
    25. int rRand = LinkeRandsumme(a, mitte + 1, endpos);
    26. int sumRaender = lRand + rRand;
    27. int lhaelfte = maxSubArray(a, startpos, mitte);
    28. int rhaelfte = maxSubArray(a, mitte + 1, endpos);
    29. System.out.println("Startposition:" + startpos + " Mitte: " + mitte
    30. + " Endposition: " + endpos);
    31. System.out.println("Linke Hälfte: " + lhaelfte);
    32. System.out.println("Rechte Hälfte: " + rhaelfte);
    33. System.out.println("LinkeRandsumme:" + lRand
    34. + " + RechteRandsumme: " + rRand + " = " + sumRaender);
    35. return max(lhaelfte, rhaelfte, lRand + rRand);
    36. }
    37. }
    38. private static int RechteRandsumme(int a[], int start, int ende) {
    39. int max = 0;
    40. int sum = 0;
    41. for (int i = ende; i >= start; i--) {
    42. sum += a[i];
    43. if (sum > max) {
    44. max = sum;
    45. }
    46. }
    47. return max;
    48. }
    49. private static int LinkeRandsumme(int a[], int start, int ende) {
    50. int max = 0;
    51. int sum = 0;
    52. for (int i = start; i <= ende; i++) {
    53. sum += a[i];
    54. if (sum > max) {
    55. max = sum;
    56. }
    57. }
    58. return max;
    59. }
    60. private static int max(int a, int b, int c) {
    61. int max0 = (a > b) ? a : b;
    62. int max = (max0 > c) ? max0 : c;
    63. return max;
    64. }
    65. }
    Alles anzeigen
  • alternative Lösung mit Kommentaren

    hier meine Lösung für alle, die noch nicht so ganz durchblicken. Ich hoffe, die Kommentare erklären das Programm adäquat:

    Quellcode

    1. /**
    2. * Algorithmen und Datenstrukturen<br>
    3. * FH-Wiesbaden, Sommersemester 2006<br>
    4. * Uebung04/Aufgabe02 - Rekursive Berechnung eines maximalen sub.Arrays<br>
    5. *
    6. * @author Sebastian Schmitt
    7. * @version 1.0
    8. */
    9. package Aufgabe02;
    10. import fhw.*;
    11. public class MaxSubArrayRekursiv {
    12. /**
    13. * @param args Kommandozeilenparameter
    14. */
    15. public static void main(String[] args) {
    16. ADSTool.resetTime();
    17. int a[];
    18. a=ADSTool.readIntArray("u4a1.dat");
    19. int ergebniss=maxSubRec(a);
    20. System.out.println(ergebniss);//46610
    21. System.out.print("Zeit: "+ADSTool.stringRTime());//0.03s !!!
    22. }
    23. /**
    24. * errechnet die maximale linke Randsumme eines int[]
    25. * @param a int[]
    26. * @return maximale linke Randsumme von a[]
    27. */
    28. static int maxSumLeft(int [] a){
    29. int max=0;
    30. int tmp=0;
    31. for(int i=0; i<a.length; i++){
    32. tmp+=a[i];
    33. if(tmp>max)
    34. max=tmp;
    35. }
    36. return max;
    37. }
    38. /**
    39. * errechnet die maximale rechte Randsumme eines int[]
    40. * @param a int[]
    41. * @return maximale rechte Randsumme von a[]
    42. */
    43. static int maxSumRight(int a[]){
    44. int max=0;
    45. int tmp=0;
    46. for(int i=a.length-1; i>0; i--){
    47. tmp+=a[i];
    48. if(tmp>max)
    49. max=tmp;
    50. }
    51. return max;
    52. }
    53. /**
    54. * errechnet das maximale sub-Array eines int[]
    55. * @param a int[]
    56. * @return maximales sub-array von a[]
    57. */
    58. static int maxSubRec(int[] a){
    59. if(a.length==1)
    60. return a[0]>0 ? a[0] : 0;
    61. else{
    62. int[] b=new int[a.length/2];
    63. System.arraycopy(a,0,b,0,a.length/2);//linke Haelfte von a[]
    64. int[] c=new int[a.length-a.length/2];
    65. System.arraycopy(a,a.length/2,c,0,a.length-a.length/2);//rechte Haelfte von a[]
    66. int maxa=0;
    67. maxa=maxSumRight(b)+maxSumLeft(c);//linke + rechte Randsumme
    68. int maxb=maxSubRec(b);//"eine Stufe Tiefer" in die linke H. von a[]
    69. int maxc=maxSubRec(c);//"eune Stufe Tiefer" in die rechte H. von a[]
    70. //return Maximum(maxa/maxb/maxc) fuer uebergeordete Rekursionen
    71. if(maxa>=maxb && maxa>=maxc)
    72. return maxa;
    73. else if(maxb>=maxa && maxb>=maxc)
    74. return maxa;
    75. else
    76. return maxc;
    77. }
    78. }
    79. }
    Alles anzeigen
  • Lösung mit Indizes-Angabe

    Hier mal meine Lösung, die neben der größten Teilsumme auch noch deren Anfangs- und Endindex ausgibt:

    Quellcode

    1. package aufgabe2;
    2. import fhw.*;
    3. /**
    4. * FH Wiesbaden, FB 06, Medieninformatik, Algorithmen und Datenstrukturen, SS 2006<br>
    5. * Uebungsblatt 4, Aufgabe 2<br><br>
    6. *
    7. * Programm, das rekursiv die maximale Teilsumme eines Arrays mit n ganzen Zahlen findet
    8. * und die Summe, sowie die Indizes der Teilfolge ausgibt<br>
    9. * Eingabe: <br>
    10. * Ausgabe: <br><br>
    11. *
    12. * Getestet mit Microsoft Windows XP Media Center Edition, Java-Version 1.5.0_05<br>
    13. *
    14. * @author Phibee
    15. * @version 1.0 (28.04.2006)
    16. */
    17. public class MaxSubArrayRekArray {
    18. /**
    19. * Startroutine des Programms
    20. * @param args Kommandozeilenparameter
    21. */
    22. public static void main(String[] args) {
    23. int[] a = ADSTool.readIntArray("u4a1simple.dat");
    24. int[] max = {0,0,0};
    25. max[0] = getMaxSubArray(a, 0, a.length-1)[0];
    26. max[1] = getMaxSubArray(a, 0, a.length-1)[1];
    27. max[2] = getMaxSubArray(a, 0, a.length-1)[2];
    28. System.out.println("Teilfolge von "+max[0]+" bis "+max[1]+" maximal mit Wert: "+max[2]);
    29. } // Ende main
    30. /**
    31. * Methode, die rekursiv die maximale Teilsumme eines Arrays mit n ganzen Zahlen findet
    32. * @param a Array
    33. * @param start Startindex
    34. * @param ende Endindex
    35. * @return Array mit groesster Teilsumme und deren Indizes
    36. */
    37. public static int[] getMaxSubArray(int[] a, int start, int ende) {
    38. int[] max = {0,0,0};
    39. if (start==ende) {
    40. if (a[start]>0) {
    41. max[0]=start;
    42. max[1]=ende;
    43. max[2]=a[start];
    44. }
    45. else {
    46. max[0]=start;
    47. max[1]=ende;
    48. max[2]=0;
    49. }
    50. return max;
    51. }
    52. else {
    53. int[] schnittstelle = new int[3];
    54. schnittstelle[0]=rechteRandsumme(a,start,(start+ende)/2)[0];
    55. schnittstelle[1]=linkeRandsumme(a,(start+ende)/2+1,ende)[1];
    56. schnittstelle[2]=rechteRandsumme(a,start,(start+ende)/2)[2]+
    57. linkeRandsumme(a,(start+ende)/2+1,ende)[2];
    58. return (max((getMaxSubArray(a,start,(start+ende)/2)),
    59. schnittstelle,
    60. getMaxSubArray(a,(start+ende)/2+1,ende)));
    61. }
    62. } // Ende getMaxSubArray
    63. /**
    64. * Methode zur Bestimmung der groessten dreier Teilsummen
    65. * @param a groesste Teilsumme der linken Haelfte
    66. * @param b Summe der groessten linken Randsumme der rechten Haelfte
    67. * und der groessten rechten Randsumme der linken Haelfte
    68. * @param c groesste Teilsumme der rechten Haelfte
    69. * @return Array mit groesster der 3 Teilsummen und deren Indizes
    70. */
    71. public static int[] max(int[] a, int[] b, int[] c) {
    72. int[] max={0,0,0};
    73. if (a[2]>b[2]) {
    74. if (a[2]>c[2]) max=a;
    75. }
    76. else if (b[2]>c[2]){
    77. max=b;
    78. }
    79. else max=c;
    80. return max;
    81. }
    82. /**
    83. * linke Randsumme des rechten Teilarrays
    84. * @param a Array
    85. * @param start Startindex
    86. * @param ende Endindex
    87. * @return Array mit groesster Randsumme und deren Indizes
    88. */
    89. public static int[] linkeRandsumme(int[] a, int start, int ende) {
    90. int sum=0;
    91. int[] max={start,start,0};
    92. for (int i=start ; i<=ende ; i++) {
    93. sum+=a[i];
    94. if (sum>max[2]) {
    95. max[0]=start;
    96. max[1]=i;
    97. max[2]=sum;
    98. }
    99. }
    100. return max;
    101. }
    102. /**
    103. * rechte Randsumme des linken Teilarrays
    104. * @param a Array
    105. * @param start Anfangsindex
    106. * @param ende Endindex
    107. * @return Array mit groesster Randsumme und deren Indizes
    108. */
    109. public static int[] rechteRandsumme(int[] a, int start, int ende) {
    110. int sum=0;
    111. int[] max={ende,ende,0};
    112. for (int i=ende ; i>=start ; i--) {
    113. sum+=a[i];
    114. if (sum>max[2]) {
    115. max[0]=i;
    116. max[1]=ende;
    117. max[2]=sum;
    118. }
    119. }
    120. return max;
    121. }
    122. } // Ende MaxSubArrayRek
    Alles anzeigen