Maximale Subaarrray -Summe in Java: Kadanes Algorithmus

Lassen Sie uns lernen, wie Sie die maximale Subaarrray -Summe mit Kadanes Algorithmus in Java effizient finden.

Problemanweisung:

Schreiben Sie ein Java -Programm, um die maximale Summe eines zusammenhängenden Subarrays mit dem Algorithmus von Kadane zu bestimmen.

Beispiel:

<code>Input:
n = 5
arr[] = 1, 2, 3, -2, 5

Output:
Maximum Subarray sum is: 9</code>

Kadanes Algorithmus verstehen:

Kadanes Algorithmus liefert eine effiziente O (N) -Komplexitätslösung für die Ermittlung der maximalen Subare -Summe.

Schritte:

1. Initialisieren Sie zwei Variablen: currentSum (um die Summe des aktuellen Subtarrays zu verfolgen) und maxSum (um die bisher auftretende maximale Summe zu speichern). Setzen Sie currentSum auf 0 und maxSum auf den kleinstmöglichen Ganzzahlwert (z. B. Integer.MIN_VALUE).

2. durch das Array iterieren: Fügen Sie für jedes Element arr[i] seinen Wert zu currentSum.

   hinzu

3. update maxSum: Aktualisieren Sie nach jeder Hinzufügung maxSum, indem Sie das Maximum von maxSum und currentSum.

4. Zurücksetzen

   : Wenn currentSum negativ wird, setzen Sie es auf 0 zurück. Dies ist entscheidend, da ein negativer currentSum angibt, dass die Einbeziehung der vorherigen Elemente nicht zu einer größeren Summe beiträgt. Es ist besser, ein neues Subtarray aus dem aktuellen Element zu starten. currentSum

Java -Code:

import java.util.Scanner;

public class KadaneAlgo {
    public static int findMaxSubArraySum(int[] arr, int n) {
        int currentSum = 0;
        int maxSum = Integer.MIN_VALUE; // Initialize to the smallest possible integer

        for (int i = 0; i < n; i++) {
            currentSum += arr[i];
            maxSum = Math.max(maxSum, currentSum); // Update maxSum if necessary
            if (currentSum < 0) {
                currentSum = 0; // Reset currentSum if it becomes negative
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the size of the array: ");
        int n = scanner.nextInt();
        int[] arr = new int[n];
        System.out.print("Enter the elements of the array: ");
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        int maxSum = findMaxSubArraySum(arr, n);
        System.out.println("Maximum Subarray sum is: " + maxSum);
        scanner.close();
    }
}

Ausgabe (Beispiel):

<code>Enter the size of the array: 5
Enter the elements of the array: 1 2 3 -2 5
Maximum Subarray sum is: 9</code>

Das obige ist der detaillierte Inhalt vonMaximale Subaarrray -Summe in Java: Kadanes Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!