Java中的最大子陣列總和：Kadane的算法

>讓我們學習如何使用java中的kadane算法有效地找到最大子陣列總和。

問題語句：

給定尺寸n的數組，編寫一個Java程序，以確定使用Kadane算法的連續子陣列的最大總和。

>示例：

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

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

了解Kadane的算法： Kadane的算法提供了有效的O（n）時間複雜度解決方案，以找到最大的子陣列總和。

步驟：

>初始化兩個變量：

（跟踪當前子陣列的總和）和
1. （存儲到目前為止遇到的最大總和）。 設置

   到0和currentSum到最小的整數值（例如，maxSum）。 currentSum> maxSum Integer.MIN_VALUE

   迭代通過數組：對於每個元素
，將其值添加到
2. >。

   > arr[i] currentSum

   > update
：每次添加後，更新
3. 最大

   和maxSum>。 maxSum>。 maxSum currentSum

   reset
：如果
4. 變為負​​，則將其重置為0。這很重要，因為負

   表明包括先前的元素不會造成更大的總和；最好從當前元素啟動一個新的子陣列。 currentSum currentSum currentSum

> java代碼：

>輸出（示例）：

<code class="language-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();
    }
}</code>

以上是Java中的最大子陣列總和：Kadane的算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！