问题描述: 给定文件data.txt,data.txt的每一行是一个数字,在这些数字按行序构成的数组中找到一个子数组,使得子数组中的元素和最大。
#include <stdio.h>
#include <stdlib.h>
int a[666666]; //定义全局数组,储存测试数据
struct Triple { //三元组,储存最大子数组的左边界、右边界及求和
int low; //最大子数组的左边界下标
int high; //最大子数组的右边界下标
int sum; //最大子数组各元素之和
}Triple;
//返回跨越数组中点的最大子数组
struct Triple maxCrossingSubArray(int a[], int low, int mid, int high) {
//求a[low..mid]的以a[mid]为右侧边界的最大子数组
int maxLeft; //记录最大子数组左侧边界的下标
int leftSum = -10000; //记录a[low..mid]中找到的最大和
int sum = 0; //记录a[low..mid]中所有值的和
int i;
for (i = mid; i >= low; i--) {
sum += a[i];
if (sum > leftSum) {
leftSum = sum;
maxLeft = i;
}
}
//求a[mid+1..high]的以a[mid+1]为左侧边界的最大子数组
int maxRight; //记录最大子数组右侧边界的下标
int rightSum = -10000; //记录a[mid+1..high]中找到的最大和
sum = 0; //记录a[mid+1..high]中所有值的和
for (i = mid+1; i <= high; i++) {
sum += a[i];
if (sum > rightSum) {
rightSum = sum;
maxRight = i;
}
}
//以三元组形式储存找到的最大子数组并返回
struct Triple t;
t.low = maxLeft;
t.high = maxRight;
t.sum = leftSum + rightSum;
return t;
}
//返回a[]的最大子数组
struct Triple maxSumSubArray(int a[], int low, int high) {
if (high == low) { //数组a[]中只有一个元素
struct Triple t;
t.low = low;
t.high = high;
t.sum = a[low];
return t;
}
else {
int mid = (low + high) / 2;
struct Triple left = maxSumSubArray(a, low, mid);//寻找完全位于a[low..mid]的最大子数组
struct Triple right = maxSumSubArray(a, mid+1, high);//寻找完全位于a[mid+1..high]的最大子数组
struct Triple cross = maxCrossingSubArray(a, low, mid, high);//寻找跨越终点的最大子数组
if (left.sum >= right.sum && left.sum >= cross.sum) {
return left;
}
else if (right.sum >= left.sum && right.sum >= cross.sum) {
return right;
}
else {
return cross;
}
}
}
int main() {
FILE *fp = fopen("data.txt","r"); //打开文件
if (fp == NULL) {
printf("Can not open the file!\n");
exit(0);
}
int i = 0;
while (fscanf(fp, "%d\n", &a[i]) != EOF) { //读取文件中的数据到数组a[]中
i++;
}
fclose(fp); //关闭文件
struct Triple result = maxSumSubArray(a, 0, i-1);
printf("low: %d\nhigh: %d\nsum: %d\n", result.low, result.high, result.sum);
return 0;
}
测试数据data.txt可在本文所附资源处下载,运行结果如下图所示: