用C语言编写给出一个数组A[0..n-1],求数组A中和最大的连续子数组。第1行为一个正整数N(N<=100000),表示数组元素个数。 第2行为数组的N个元素,每个元素为整数,相互之间用空格分隔。在一行中输出最大子数组的起始下标、结束下标和子数组的和,用空格分开。
时间: 2024-03-11 08:50:55 浏览: 48
好的,以下是 C 语言代码实现:
```c
#include <stdio.h>
int main() {
int n, i, max_sum, cur_sum, start_index, end_index, cur_index;
scanf("%d", &n);
int arr[n];
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
max_sum = cur_sum = arr[0];
start_index = end_index = cur_index = 0;
for (i = 1; i < n; i++) {
if (cur_sum < 0) {
cur_sum = arr[i];
cur_index = i;
} else {
cur_sum += arr[i];
}
if (cur_sum > max_sum) {
max_sum = cur_sum;
start_index = cur_index;
end_index = i;
}
}
printf("%d %d %d", start_index, end_index, max_sum);
return 0;
}
```
这个算法的时间复杂度是 O(n),其中 n 是数组的长度。
阅读全文