数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Java 中的最大子数组和：Kadane 算法
在这里，我们将学习如何使用 Java 中的 Kadane 算法查找最大子数组和？
问题陈述
给定一个大小为 N 的数组，编写一个 Java 程序，使用 Kadane 算法查找最大子数组和。
示例
Input: n = 5 arr[] = 1, 2, 3, -2, 5 Output: Maximum Subarray sum is: 9
什么是 Kadane 算法
Kadane 算法帮助我们以 O(n) 的时间复杂度找到最大子数组和。
使用 Kadane 算法查找最大子数组和的步骤
- 初始化两个名为 currentSum=Integer.MIN_VALUE 和 maxSum= 0 的变量。
- 迭代数组，从索引 0 到 n-1。
- 将每个索引的值 (arr[i]) 添加到 currentSum 中。
- 在每次迭代中更新 maxSum Math.max(maxSum, currentSum)。
- 检查 currentSum 是否小于零，如果小于零，则赋值 currentSum = 0。
这里主要是要将 currentSum 赋值为零，因为我们正在查找最大和，如果和变为小于零，则继续保留它没有意义。我们只需将 currentSum 重置为零，然后从一个新的子数组开始。
使用 Kadane 算法查找最大子数组和的 Java 代码
import java.util.Scanner;
public class KadaneAlgo {
static int FindMaxSubArraySum(int[] arr, int n) {
int currentSum = 0, maxSum = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
currentSum = Math.max(arr[i], currentSum + arr[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the size of array: ");
int n = sc.nextInt();
int[] arr = new int[n];
System.out.println("Enter " + n + " Array elements: ");
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
long maxSum = FindMaxSubArraySum(arr, n);
System.out.println("Max Subarray Sum is: " + maxSum);
}
}
输出
更新于: 2024-09-09
108 次浏览
广告