Heim > Java > javaLernprogramm > Maximale Subaarrray -Summe in Java: Kadanes Algorithmus

Maximale Subaarrray -Summe in Java: Kadanes Algorithmus

Barbara Streisand
Freigeben: 2025-02-07 11:54:19
Original
825 Leute haben es durchsucht

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>
Nach dem Login kopieren

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();
    }
}
Nach dem Login kopieren

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>
Nach dem Login kopieren

Maximum Subarray Sum in Java: Kadane’s Algorithm

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!

Verwandte Etiketten:
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Neueste Artikel des Autors
Aktuelle Ausgaben
Kann Java als Backend des Webs verwendet werden?
Aus 1970-01-01 08:00:00
0
0
0
Installieren Sie JAVA
Aus 1970-01-01 08:00:00
0
0
0
Java kann nicht installiert werden
Aus 1970-01-01 08:00:00
0
0
0
Ist das in der Java-Sprache?
Aus 1970-01-01 08:00:00
0
0
0
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage