java代码编写:给定由 n 个整数(可能为负整数)组成的序列,求解其连续的最大字段和。当所有数都是负整数时,最大字段和是 0 ,序列采用键盘输入
时间: 2024-09-24 16:30:10 浏览: 44
在 Java 中,我们可以使用 Kadane 算法(动态规划的一种形式)来解决这个问题。这个算法用于在一个数组或列表中找到非降序子序列的最大和。以下是 Java 代码实现:
```java
import java.util.Scanner;
public class MaxSubarraySum {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入数字的数量(n):");
int n = scanner.nextInt();
// 初始化一个长度为 n 的变量数组,用于存储当前的子序列和
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
System.out.print("请输入第 " + (i+1) + " 个数:");
nums[i] = scanner.nextInt();
}
// 使用 Kadane 算法计算最大子数组和
int maxSoFar = nums[0]; // 当前最大和
int maxEndingHere = nums[0]; // 从当前位置开始的最大子数组和
for (int i = 1; i < n; i++) {
maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]); // 更新当前结束点的最大和
maxSoFar = Math.max(maxSoFar, maxEndingHere); // 更新全局最大和
}
// 输出结果
if (maxSoFar <= 0) {
System.out.println("由于全是负数,最大字段和为 0");
} else {
System.out.println("连续的最大字段和是: " + maxSoFar);
}
scanner.close();
}
}
```
在这个程序中,我们首先读取用户输入的 n 和 n 个整数,然后通过遍历数组并更新 `maxEndingHere` 和 `maxSoFar` 来找到最大子数组和。如果最终的最大和小于等于0,则说明全是负数,所以最大字段和就是0。
阅读全文