C语言编写程序找出序列的最大子段和,以及子段的起始位置和结束位置。例如:输入数组(6,-1,5,4,-7),输出14, 1, 4,其中14表示最大子段和,1表示和最大的子段从第1个数字开始,4表示和最大的子段到第4个数字结束。
时间: 2024-05-05 18:16:59 浏览: 107
以下是C语言实现:
```c
#include <stdio.h>
int main() {
int n = 5;
int a[] = {6, -1, 5, 4, -7};
int sum = 0;
int maxSum = 0;
int start = 0;
int end = 0;
int i = 0;
for (i = 0; i < n; i++) {
if (sum > 0) {
sum += a[i];
} else {
sum = a[i];
start = i;
}
if (sum > maxSum) {
maxSum = sum;
end = i;
}
}
printf("%d %d %d\n", maxSum, start + 1, end + 1);
return 0;
}
```
解释:
我们使用了Kadane算法来解决这个问题。该算法可以在线性时间内找到最大子段和。
我们定义两个变量sum和maxSum,分别表示当前子段的和和最大子段和。我们遍历整个数组,如果当前子段的和sum大于0,则将当前数字加入子段中;否则,将当前数字作为新的子段的起点。在每次更新sum的同时,比较sum和maxSum,更新maxSum和end的值。
最后,我们输出maxSum、start和end的值,其中start和end分别加1表示子段的起始位置和结束位置。
阅读全文