分治法 —— 最大子段和

最大子段和

给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。(题面即解释)

现在我们可以将题目分为几个部分来看。
1. 左段：left – mid部分的最大值
2. 右段： mid+1 – right部分的最大值
3. 将中间两段合并的最大值

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;

ll a[200010], n;
const ll minnum = -999999;

ll max_sum(ll left, ll right)
{
    if (left == right) return a[left];
    ll mid = (left + right) / 2;
    ll sum1 = 0, sum2 = 0;
    ll sum_left = minnum, sum_right = minnum;
    for (ll i = mid; i >=left; i--)            //从left - mid的最大值
    {
        sum1 += a[i];
        sum_left = max(sum_left, sum1);
    }
    for (ll i = mid + 1; i <= right; i++)      //从mid+1 - right的最大值
    {
        sum2 += a[i];
        sum_right = max(sum_right, sum2);
    }
    return max(max(max_sum(left, mid), max_sum(mid + 1, right)), sum_left + sum_right);    //第3种情况为中间合并时的值，将其3种情况比较最大值

}


int main()
{
    cin >> n;
    for (ll i = 1; i <= n; i++)
        cin >> a[i];
    cout << max_sum(1, n) << endl;
    return 0;
}

运行结果：