编写java程序找出序列的最大子段和,以及子段的起始位置和结束位置。例如:输入数组(6,-1,5,4,-7),输出14, 1, 4,其中14表示最大子段和,1表示和最大的子段从第1个数字开始,4表示和最大的子段到第4个数字结束
时间: 2024-05-01 13:21:09 浏览: 17
以下是一个Java程序,可以找出给定数组的最大子段和及其起始位置和结束位置:
```java
public class MaxSubArray {
public static void main(String[] args) {
int[] arr = {6, -1, 5, 4, -7};
int[] result = maxSubArray(arr);
System.out.println("最大子段和:" + result[0]);
System.out.println("子段起始位置:" + result[1]);
System.out.println("子段结束位置:" + result[2]);
}
public static int[] maxSubArray(int[] arr) {
int maxSum = Integer.MIN_VALUE;
int maxStart = 0;
int maxEnd = 0;
int currentSum = 0;
int currentStart = 0;
for (int i = 0; i < arr.length; i++) {
currentSum += arr[i];
if (currentSum > maxSum) {
maxSum = currentSum;
maxStart = currentStart;
maxEnd = i;
}
if (currentSum < 0) {
currentSum = 0;
currentStart = i + 1;
}
}
return new int[]{maxSum, maxStart, maxEnd};
}
}
```
程序中的 `maxSubArray` 方法使用 Kadane 算法实现,时间复杂度为 O(n)。该算法的基本思想是维护一个当前子段和的最大值和当前子段的起始位置,依次遍历数组,如果当前子段和大于最大值,则更新最大值和起始位置;如果当前子段和小于 0,则舍弃之前的子段,将起始位置移动到下一个位置。最后返回最大值和起始位置、结束位置的数组。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)