Java 给定一个整数数组nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大值和最小值
时间: 2024-06-15 14:09:02 浏览: 193
给定一个整数数组nums,要找到具有最大和的连续子数组,可以使用动态规划的方法来解决。我们可以定义两个变量maxSum和curSum,分别表示当前的最大和和当前的累加和。
首先,将maxSum和curSum都初始化为数组的第一个元素nums。然后,从数组的第二个元素开始遍历,对于每个元素nums[i],我们有两种选择:
1. 将当前元素加入到当前的累加和curSum中,即curSum = curSum + nums[i]。
2. 将当前元素作为新的起点,重新计算累加和curSum,即curSum = nums[i]。
然后,比较当前的累加和curSum和最大和maxSum的大小,如果curSum大于maxSum,则更新maxSum为curSum。
最后,遍历完整个数组后,maxSum就是最大和的连续子数组的和。
至于最小值,我们可以在遍历过程中同时记录最小值minVal。每次更新maxSum时,也可以更新minVal为当前的最小值。
下面是Java代码实现:
```java
public int[] findMaxSubarray(int[] nums) {
int maxSum = nums[0];
int curSum = nums[0];
int minVal = nums[0];
int[] result = new int[2];
result[0] = maxSum; // 最大和
result[1] = minVal; // 最小值
for (int i = 1; i < nums.length; i++) {
curSum = Math.max(curSum + nums[i], nums[i]);
maxSum = Math.max(maxSum, curSum);
minVal = Math.min(minVal, curSum);
}
result[0] = maxSum;
result[1] = minVal;
return result;
}
```
阅读全文