#include <stdio.h>
typedef struct {
size_t st;
size_t end;
int sum;
} ArraySection;
/* 求整型数组的最大子段和，结果存于ret */
void max_section(int *arr, size_t len, ArraySection *ret) {
size_t st = 0, end = 0;
int sum = *arr;// sum：以当前元素为结尾的所有子段中，子段和最大者
size_t i;
ret->st = ret->end = 0;
ret->sum = sum;
for (i = 1; i < len; ++i) {
if (sum < 0) {
sum = arr[i];
end = st = i;
} else {
++end;
sum += arr[i];
}
if (sum > ret->sum) {
ret->st = st;
ret->end = end;
ret->sum = sum;
}
}
}
/* 测试代码 */
int main() {
ArraySection as = { 0, 0, 0 };
int arr[] = { -12, 23, 34, -4, -12, 128 };
max_section(arr, sizeof(arr) / sizeof(*arr), &as);
printf("st=%u\nend=%u\nsum=%i\n", as.st, as.end, as.sum);
return 0;
}
| 
转播
