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
Alles anzeigen
(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
- public class A04_Maximium_Sub_Array {
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- int[] a = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
- naiv(a);
- }
- /**
- * Liefert die Summe der Elemente einer Teilfolge
- * @param a
- */
- static void naiv(int[] a)
- {
- int startindex=0, endindex=0, max=0;
- for(int i=0; i<a.length; i++) {
- int summe=0;
- for(int j=i; j<a.length; j++) {
- summe += a[j];
- if(summe > max) {
- max = summe;
- startindex = i;
- endindex = j;
- }
- }
- }
- System.out.println("max: "+max);
- System.out.println("von "+startindex+" bis "+endindex);
- }
- }