Subarray Maksimum Jawa: Algoritma Kadane

mari kita belajar bagaimana untuk mencari jumlah subarray maksimum menggunakan algoritma Kadane di Java.

Pernyataan Masalah:

Diberi pelbagai saiz n, tulis program Java untuk menentukan jumlah maksimum subarray bersebelahan menggunakan algoritma Kadane.

Contoh:

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

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

Memahami algoritma Kadane:

Algoritma Kadane menyediakan penyelesaian kerumitan masa O (n) yang cekap untuk mencari jumlah subarray maksimum.

Langkah -langkah:

1. Inisialisasi dua pembolehubah:

   (untuk menjejaki jumlah subarray semasa) dan currentSum (untuk menyimpan jumlah maksimum yang ditemui setakat ini). Tetapkan maxSum hingga 0 dan currentSum ke nilai integer yang paling kecil (mis., ). maxSum Integer.MIN_VALUE

Melangkah melalui array: Untuk setiap elemen
2. , tambahkan nilainya ke

   . arr[i] currentSum

UPDATE
3. : Selepas setiap penambahan, kemas kini

   dengan mengambil maksimum maxSum dan maxSum. maxSum currentSum

Reset
4. : Jika

   menjadi negatif, tetapkan semula kepada 0. Ini adalah penting kerana negatif currentSum menunjukkan bahawa termasuk unsur -unsur sebelumnya tidak menyumbang kepada jumlah yang lebih besar; lebih baik memulakan subarray baru dari elemen semasa. currentSum 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();
    }
}

output (Contoh):

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

Atas ialah kandungan terperinci Subarray Maksimum Jawa: Algoritma Kadane. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!