c++运用分治法写最大序列和问题

最大序列和问题可以使用分治法来解决。具体步骤如下：

1. 将序列平均分成两部分。

2. 分别递归求解左半部分和右半部分的最大序列和。

3. 以中间点为界，分别向左和向右扫描，求出跨越中间点的最大序列和。

4. 比较三个结果，取最大值作为最终结果。

下面是c++代码实现：

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

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

    sum = 0;
    int right_sum = INT_MIN;
    for (int i = m + 1; i <= h; i++)
    {
        sum += arr[i];
        if (sum > right_sum)
            right_sum = sum;
    }

    return left_sum + right_sum;
}

int maxSubArraySum(int arr[], int l, int h)
{
    if (l == h)
        return arr[l];

    int m = (l + h) / 2;

    int left_sum = maxSubArraySum(arr, l, m);
    int right_sum = maxSubArraySum(arr, m + 1, h);
    int cross_sum = maxCrossingSum(arr, l, m, h);

    return max({ left_sum, right_sum, cross_sum });
}

int main()
{
    int n;
    cout << "请输入序列长度：";
    cin >> n;
    int arr[n];
    cout << "请输入序列：";
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    int max_sum = maxSubArraySum(arr, 0, n - 1);
    cout << "最大序列和为：" << max_sum << endl;

    return 0;
}

输入样例：

请输入序列长度：8
请输入序列：-2 1 -3 4 -1 2 1 -5

输出样例：

最大序列和为：6