【编程之美】 2.14 求数组的子数组之和的最大值

发表于

普通法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxSum_w1(int a[],int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int tempsum = 0;
        for (int j = i; j < n;j++) {
            //add i to j
            tempsum += a[j];
            if (tempsum > sum) {
                sum = tempsum;
            }
        }
    }
    return sum;
}

分治法

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
    if (left == right) { return a[left]; }
    if (right - left + 1 == 2) {
        int maxelement = std::max(a[left], a[right]);
        return std::max(maxelement, a[left] + a[right]);
    }
    int result_left = recursion(a, n, left, (right+left)/2 );
    int result_right = recursion(a, n, (right + left) / 2 + 1, right);

    int mix_left = a[left + (right - left) / 2];
    int mix_right = a[left + (right - left) / 2 + 1];

    int temp = 0;
    for (int i = left + (right-left)/2; i >= left; i--) {
        temp += a[i];
        if (temp > mix_left) { mix_left = temp; }
    }

    temp = 0;
    for (int i = left + (right - left) / 2+1; i <= right; i++) {
        temp += a[i];
        if (temp > mix_right) { mix_right = temp; }
    }

    int max_temp = std::max(result_left, result_right);

    return std::max(mix_left + mix_right, max_temp);
}

int maxSum_w3(int a[], int n) {
    return   recursion(a, n, 0, n -1);
}

动态规划法

1
2
3
4
5
6
7
8
9
10
11
int maxSum_w2(int a[], int n) {
    if (n <= 1) { return -1000; }
    int all=a[n-1];
    int result=a[n-1];
    if (n <= 2) { return result; }
    for (int i = n - 2; i >= 0; i--) {
        all = std::max(a[i], a[i] + all);
        result = std::max(result, all);
    }
    return result;
}

其中动态规划是时间复杂度最低的，而且代码也较短。相对而言分治法可能会产生更多的bug。

note:可以建立三个cpp文件，包含一个共同的头文件申明，然后主函数只要包含头文件就可以了，这样就不需要写多个main函数那么麻烦了。