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代码：

>输出（示例）：

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

以上是Java中的最大子阵列总和：Kadane的算法的详细内容。更多信息请关注PHP中文网其他相关文章！