用C语言修改最大子序列和的四个程序,显示出最大的子序列的开始和结束位置
时间: 2024-10-21 15:05:07 浏览: 42
c语言简洁实用笔记,嵌入式开发必备
在C语言中,有一个经典的算法叫做Kadane's Algorithm(凯撒和算法),用于求解给定数组的最大子序列和。以下是使用该算法的简单版本,并记录下最大子序列的起始和结束索引:
```c
#include <stdio.h>
int maxSubArray(int arr[], int size) {
int max_current = arr[0];
int max_global = arr[0];
int start = 0;
int end = 0;
for (int i = 1; i < size; i++) {
if (arr[i] > max_current + arr[i]) { // 如果当前元素直接加到前缀和比从头开始更好
max_current = arr[i]; // 更新当前连续子序列的和
start = i; // 重置开始位置
} else {
max_current += arr[i]; // 否则将当前元素添加到连续子序列
}
if (max_current > max_global) {
max_global = max_current; // 更新全局最大子序列和
end = i; // 记录结束位置
}
}
printf("最大子序列和: %d\n", max_global);
printf("子序列起始索引: %d\n", start);
printf("子序列结束索引: %d\n", end);
return max_global;
}
// 测试函数
int main() {
int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int size = sizeof(arr) / sizeof(arr[0]);
maxSubArray(arr, size);
return 0;
}
```
这个程序会找到数组`arr`中的最大子序列和以及对应的起始和结束索引。注意,由于数组越界的问题,实际编写时需要对输入数组的大小进行检查。
阅读全文