Somme maximale de la sous-bande en Java: l'algorithme de Kadane

apprenons à trouver efficacement la somme maximale de sous-réseau en utilisant l'algorithme de Kadane en Java.

Instruction Problème:

Compte tenu d'un tableau de taille n, écrivez un programme Java pour déterminer la somme maximale d'un sous-réseau contigu en utilisant l'algorithme de Kadane.

Exemple:

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

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

Comprendre l'algorithme de Kadane:

L'algorithme de Kadane fournit une solution de complexité temporelle O (n) efficace pour trouver la somme maximale de sous-réseau.

étapes:

1. Initialiser deux variables: currentSum (pour suivre la somme du sous-réseau actuel) et maxSum (pour stocker la somme maximale rencontrée jusqu'à présent). Définissez currentSum sur 0 et maxSum à la plus petite valeur entière possible (par exemple, Integer.MIN_VALUE).

2. itérer dans le tableau: pour chaque élément arr[i], ajoutez sa valeur à currentSum.

3. Mise à jour maxSum: Après chaque ajout, mise à jour maxSum en prenant le maximum de maxSum et currentSum.

4. réinitialiser currentSum: si currentSum devient négatif, réinitialisez-le à 0. Ceci est crucial car un négatif currentSum indique que l'inclusion des éléments précédents ne contribue pas à une somme plus grande; Il vaut mieux démarrer un nouveau sous-réseau à partir de l'élément actuel.

Code java:

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();
    }
}

sortie (exemple):

<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>

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!