Java给定由 n 个整数(可能为负整数)组成的序列,求解其连续的最大字段和。当所有数都是负整数时,最大字段和是 0 .
时间: 2024-09-30 14:13:12 浏览: 30
任意给定 n 个整数,求这 n 个整数序列的和、最小值、最大值
在Java中,计算给定数组的连续最大子数组和(也称为“ Kadane's algorithm”)是一个常见的动态规划问题。以下是算法的基本步骤:
1. 定义两个变量:`current_sum` 和 `max_sum`,初始值都为数组的第一个元素。
2. 遍历数组从第二个元素开始:
- 计算当前子数组的和 (`current_sum`),等于前一个 `current_sum` 加上当前元素。如果当前元素大于0,则直接加上当前元素;否则,将 `current_sum` 设为当前元素,因为负数会使得连续和减小。
- 比较 `current_sum` 和 `max_sum`,更新较大的一个作为新的 `max_sum`。
3. 当遍历完数组后,`max_sum` 就是最长连续正数子数组的和,如果所有数都是负数,那么结果就是0。
以下是Java代码实现示例:
```java
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int current_sum = nums[0];
int max_sum = current_sum;
for (int i = 1; i < nums.length; i++) {
current_sum = Math.max(nums[i], current_sum + nums[i]);
max_sum = Math.max(max_sum, current_sum);
}
return max_sum;
}
```
阅读全文