跳转至

最大子数组

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#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;
}