java找出一个整数数组中子数组之和的最大值,例如:数组,返回8(因为符合要求的子数组是);数组,返回6(因为符合要求的子数组是 ); 数组,返回7(因为符合要求的子数组是 )。
时间: 2024-09-17 07:06:06 浏览: 53
在Java中,可以使用动态规划算法来找到给定整数数组中所有连续子数组的和的最大值。这种做法通常用于解决“最大子数组和”问题。下面是一个简单的解决方案:
```java
public int maxSubArraySum(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int maxSoFar = nums[0];
int maxEndingHere = nums[0];
for (int i = 1; i < nums.length; i++) {
maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
```
这个函数`maxSubArraySum`遍历数组,对于每个元素,它要么选择当前元素作为新开始的新子数组,要么选择将当前元素添加到前一个最大子数组的和中。然后更新全局最大子数组和`maxSoFar`。
对于给出的例子:
- 对于数组 [1, -2, 3, 4, -5],最大子数组和是8,由子数组 [3, 4] 给出;
- 对于数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4],最大子数组和是6,由子数组 [4, -1, 2, 1] 或者 [4, -1, 2, 1, -5, 4] 给出;
- 对于数组 [1, 2, -3, 4, 5],最大子数组和是7,由子数组 [1, 2, -3, 4] 给出,注意这里负数不会破坏整体的最大和。
阅读全文