Maximum Sub Array Problem

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

    Gegeben sei ein Feld n ganzen Zahlen. Suchen Sie eine zusammenhängende Teilfolge, so dass die Summe der Elemente dieser Teilfolge maximal ist
    (Maximum-Sub-Array Problem). Zum Beispiel ist im folgenden Beispiel mit 10 Elementen, die von 0 bis 9 indiziert sind, die Lösung die Teilfolge von 2 bis 6 mit dem maximalen Wert 187.

    Hierbei handelt es sich um die iterative Lösung.
    Eine rekursive Lösung findet ihr hier: Maximum Sub Array Rekursiv

    Quellcode

    1. public class A04_Maximium_Sub_Array {
    2. public static void main(String[] args) {
    3. // TODO Auto-generated method stub
    4. int[] a = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
    5. naiv(a);
    6. }
    8. /**
    9. * Liefert die Summe der Elemente einer Teilfolge
    10. * @param a
    11. */
    12. static void naiv(int[] a)
    13. {
    14. int startindex=0, endindex=0, max=0;
    15. for(int i=0; i<a.length; i++) {
    16. int summe=0;
    17. for(int j=i; j<a.length; j++) {
    18. summe += a[j];
    19. if(summe > max) {
    20. max = summe;
    21. startindex = i;
    22. endindex = j;
    23. }
    24. }
    25. }
    26. System.out.println("max: "+max);
    27. System.out.println("von "+startindex+" bis "+endindex);
    28. }
    29. }
    Alles anzeigen