/*------------------  求解最大子数组问题  ---------------    最大子数组，就是求解一个数组的所有元素的各种组合中，和最大的那个子数组。在这种情况下，如果元素值全部非负，那么最大子数组当然是所有元素。但是如果有负值的元素存在，那么久需要找到一个由数组中连续几个元素组成的子数组并且其元素值之和最大。*/#include <iostream>using namespace std;struct ArrayStruct {    ArrayStruct(int b = 0, int e = 0, int s = 0):                begin(b), end(e), sum(s) { }    int begin;    int end;    int sum;};/*方法一： 首先，最简单的当然是暴力求解，这种情况下，算法的复杂度是ø(n^2)的，代码如函数 subArrayRough 所示。 */ArrayStruct subArrayRough(int *array, int length) {    int sum = -999999;    int begin, end;    for (int i = 0; i != length; ++i) {        int sumTemp = 0;        for (int j = i; j != length; ++j) {            sumTemp += array[j];            if (sum < sumTemp) {                begin = i;                sum = sumTemp;                end = j;            }        }    }    return ArrayStruct(begin, end, sum);}/*方法二是采用分治法：    加入我们寻找数组 A[low, high] 的最大子数组，使用分治技术意味着把原数组进行分割，也就是将原数组划分为规模尽量相同的子数组。那么，就需要找到原数组的重点 mid，然后分别对原数组的 mid 左边和右边进行处理。那么，最大子数组所处的位置必然是下面三种情况之一【i, j 为结果范围下标】：    · 完全位于子数组 A[low, mid]中，因此 low <= i <= j <= mid.    · 完全位于子数组A[mid + 1, high] 中，因此 mid < i <= j <= high.    · 跨越中点，因此 low <= i <= mid < j <= high实际上，数组 A 的最大子数组必然是上面三种情况中的最大者。那么，我们只需要找到上面三种情况的最大者即可。    那么，我们就可以递归地求解子数组 A[low, mid]，A[mid + 1, high] 的最大子数组，因为这仍然是求解最大子数组问题，然后将这两者的值和两者和中点组成的组数组三者中寻找最大值。那么，我们就要处理三种情况，A[low, mid]，A[mid + 1, high] 和包括中点三种情况。伪代码如下：FIND-MAXIMUM-SUBARRAY(A, low, high):    if high == low:        return (low, high, A[low])         // 只有一个元素，那么最大值就是这个元素值    else mid = [(low + high) / 2]        (left-low, left-high, left-sum) = FIND-MAXIMUM-SUBARRAY(A, low, mid)        (right-low, right-high, right-sum) = FIND-MAXIMUM-SUBARRAY(A, mid + 1, high)        (cross-low, cross-high, cross-sum) = FIND-MAXIMUM-CROSSING-SUBARRAY(A, low, mid, high)        if left-sum >= right-sum && left-sum >= cross-sum:            return (left-low, left-high, left-sum)        if right-sum >= right-sum && right-sum >= cross-sum:            return (right-low, right-high, right-sum)        else            return (cross-low, cross-high, cross-sum)其中，函数 FIND-MAXIMUM-CROSSING-SUBARRAY 的伪代码如下，其实它的作用就是找出一定包含 mid 元素的的最大子数组，那么久可以直接从 mid 出发去向两边查找：FIND-MAXIMUM-CROSSING-SUBARRAY(A, low, mid, high):    left-sum = -∞    sum = 0;    for i = mid downto low:        sum += A[i]        if left-sum < sum:            left-sum = sum            max-left = i    right-sum = -∞    sum = 0;    for i = mid + 1 to high:        sum += A[i]        if right-sum < sum:            right-sum = sum            max-right = i    return (max-left , max- right, left-sum + right-sum)根据伪代码不难写出代码。FIND-MAXIMUM-CROSSING-SUBARRAY 的时间复杂度是线性的，而 FIND-MAXIMUM-SUBARRAY因为是分治法，对于分治法算时间复杂度的主方法 T(n) = aT(n / b) + f(n) 可以知道，因为a == b == 2 所以时间复杂度是 log(n)，所以总的时间复杂度是 n(log(n))*/ArrayStruct findMaximumCrossingSubArray(int *array, int low, int mid, int high) {    int leftSum = -99999;    int sum = 0, leftMax = low;    for (int i = mid; i >= 0; --i) {        sum += array[i];        if (sum > leftSum) {            leftSum = sum;            leftMax = i;        }    }    int rightSum = -99999;    sum = 0;    int rughtMax = high;    for (int i = mid + 1; i <= high; ++i) {        sum += array[i];        if (sum > rightSum) {            rightSum = sum;            rughtMax = i;        }    }    return ArrayStruct(leftMax, rughtMax, leftSum + rightSum);}ArrayStruct findMaximumSubArray(int *array, int low, int high) {    if (high == low) {        return ArrayStruct(low, high, array[low]);    } else {        int mid = (low + high) / 2;        ArrayStruct left = findMaximumSubArray(array, low, mid);        ArrayStruct right = findMaximumSubArray(array, mid + 1, high);        ArrayStruct cross = findMaximumCrossingSubArray(array, low, mid, high);        if (left.sum >= right.sum && left.sum >= cross.sum)            return left;        else if (right.sum >= right.sum && right.sum >= cross.sum)            return right;        else            return cross;    }}int main(int argc, char const *argv[]){    cout << "Input the size of the array: ";    int arraySize;    int *array;    cin >> arraySize;    array = new int[arraySize];    for (int i = 0; i != arraySize; ++i)        cin >> array[i];    ArrayStruct a = subArrayRough(array, arraySize);    cout << "result of rough found: " << endl << ‘\t‘;    for(int i = a.begin; i <= a.end; ++i) {        cout << array[i] << " ";    }    cout << endl;    cout << "result of minute found: " << endl << ‘\t‘;    ArrayStruct b = findMaximumSubArray(array, 0, arraySize - 1);    for(int i = b.begin; i <= b.end; ++i) {        cout << array[i] << " ";    }    cout << endl;    return 0;}