给定由n个整数(可能有负整数)组成的序列(a(1)，a（2），…，a(n)),求该 序列形如∑a子段和的最大值。 分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法，并设计测试数据，比较不同算法的时间性能。 设b(j)表示序列(a1，a2，…，aj)的最大子段和,补充定义6(0)=0，动态规划函数如下:b（j）=b(j-1)+aj b(j-1)＞0；b(j)=a(j) b(j-1)<=0 1<=j<=n 用C++代码实现

蛮力法：

#include<iostream>
using namespace std;

int maxSubArray(int arr[], int n)
{
    int maxSum = INT_MIN;
    for (int i = 0; i < n; i++)
    {
        int sum = 0;
        for (int j = i; j < n; j++)
        {
            sum += arr[j];
            maxSum = max(maxSum, sum);
        }
    }
    return maxSum;
}

int main()
{
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum Subarray Sum: " << maxSubArray(arr, n);
    return 0;
}

分治法：

#include<iostream>
#include<climits>
using namespace std;

int maxCrossingSum(int arr[], int l, int m, int h)
{
    int sum = 0;
    int leftSum = INT_MIN;
    for (int i = m; i >= l; i--)
    {
        sum += arr[i];
        if (sum > leftSum)
            leftSum = sum;
    }
    sum = 0;
    int rightSum = INT_MIN;
    for (int i = m + 1; i <= h; i++)
    {
        sum += arr[i];
        if (sum > rightSum)
            rightSum = sum;
    }
    return leftSum + rightSum;
}

int maxSubArraySum(int arr[], int l, int h)
{
    if (l == h)
        return arr[l];
    int m = (l + h) / 2;
    return max(maxSubArraySum(arr, l, m),
               max(maxSubArraySum(arr, m + 1, h),
                   maxCrossingSum(arr, l, m, h)));
}

int main()
{
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum Subarray Sum: " << maxSubArraySum(arr, 0, n - 1);
    return 0;
}

动态规划法：

#include<iostream>
#include<climits>
using namespace std;

int maxSubArraySum(int arr[], int n)
{
    int maxSum = INT_MIN, sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += arr[i];
        maxSum = max(maxSum, sum);
        if (sum < 0)
            sum = 0;
    }
    return maxSum;
}

int main()
{
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum Subarray Sum: " << maxSubArraySum(arr, n);
    return 0;
}

测试数据：

int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int n = sizeof(arr) / sizeof(arr[0]);

不同算法的时间性能：
蛮力法：O(n^2)
分治法：O(nlogn)
动态规划法：O(n)