java代码编写:给定由 n 个整数(可能为负整数)组成的序列,求解其连续的最大字段和。当所有数都是负整数时,最大字段和是 0 . 如:a[] = {-2, 11, -4, 13, -5, -2}时, max = 11 + (-4) + 13 = 20.。
时间: 2024-09-24 11:29:01 浏览: 29
在Java中,我们可以使用动态规划来解决这个问题。我们维护两个变量:`maxSoFar` 表示当前已计算的最大和,`maxEndingHere` 表示以当前位置结束的最大连续正向子数组的和。当我们遇到负数时,`maxEndingHere` 就变为0,因为它不能再贡献新的和了;但是 `maxSoFar` 可能继续增加,直到找到下一个正数。
以下是Java代码实现:
```java
public class Solution {
public int maxSubArray(int[] nums) {
int maxSoFar = nums[0], maxEndingHere = nums[0]; // 初始化最大和为第一个数
for (int i = 1; i < nums.length; i++) {
maxEndingHere = Math.max(maxEndingHere + nums[i], nums[i]); // 更新结束于i的最大和
maxSoFar = Math.max(maxSoFar, maxEndingHere); // 更新最大和
}
return maxSoFar;
}
public static void main(String[] args) {
int[] a = {-2, 11, -4, 13, -5, -2};
Solution solution = new Solution();
System.out.println(solution.maxSubArray(a)); // 输出:20
}
}
```
这个算法的时间复杂度是O(n),其中n是数组长度,因为我们只遍历一次数组。
阅读全文
相关推荐



















