#include<iostream>
#include@H_403_23@<vector>
#include@H_403_23@<algorithm>
using@H_403_23@ namespace@H_403_23@ std;
@H_403_23@int@H_403_23@ max_sub_array(vector<int@H_403_23@>& data,int@H_403_23@ left,1)">int@H_403_23@ right);
@H_403_23@int@H_403_23@ max_crossing_sub_array(vector<int@H_403_23@ mid,1)"> right);


@H_403_23@ main()
{

    vector@H_403_23@<int@H_403_23@> data = { 3@H_403_23@,0@H_403_23@,1)">5@H_403_23@,1)">2@H_403_23@,1)">7@H_403_23@,1)">8@H_403_23@,1)">9@H_403_23@,1)">6@H_403_23@,1)">1@H_403_23@ };
    @H_403_23@//@H_403_23@获取序列元素个数@H_403_23@
    int@H_403_23@ length = 9@H_403_23@;
    @H_403_23@int@H_403_23@ left = 0@H_403_23@int@H_403_23@ right = 8@H_403_23@int@H_403_23@ sum = ;
    sum @H_403_23@= max_sub_array(data,left,right);
    cout @H_403_23@<< sum << "@H_403_23@   "@H_403_23@;
}

@H_403_23@int@H_403_23@> &data,1)"> right)
{
    @H_403_23@if@H_403_23@ (left >= right)因为这个时候表示已经分解到只剩一个元素了，就是递归的终止条件,子数组的最大值就是元素本身，返回@H_403_23@
    {
        @H_403_23@return@H_403_23@ data[left];
    }
    @H_403_23@else@H_403_23@
    {
        @H_403_23@将序列一分为二获取中间位置@H_403_23@
        int@H_403_23@ mid = (left + right) / 2@H_403_23@;
        @H_403_23@int@H_403_23@ max_left,max_right,max_cross,Smax;用来存储子数组的和
        @H_403_23@分治@H_403_23@
        max_left = max_sub_array(data,mid);左边子数组的和@H_403_23@
        max_right = max_sub_array(data,mid + 1@H_403_23@,right);右边子数组的和
        @H_403_23@合并@H_403_23@
        max_cross = max_crossing_sub_array(data,mid,1)">跨越中心的子数组的和@H_403_23@
        Smax = max(max(max_left,max_right),max_cross);
        @H_403_23@ Smax;
    }
}

@H_403_23@int@H_403_23@ left_max = -99999@H_403_23@;不可能达到的一个数@H_403_23@
    int@H_403_23@ right_max = -99999@H_403_23@/*@H_403_23@计算以mid结尾的最大的子数组和，左边子数组@H_403_23@*/@H_403_23@
    for@H_403_23@ (int@H_403_23@ i = mid; i >= left; --i) {
        sum @H_403_23@+= data.at(i);
        @H_403_23@if@H_403_23@ (sum > left_max)
            left_max @H_403_23@= sum;
    }
    sum @H_403_23@= 计算以mid+1开始的最大的子数组和，右边子数组@H_403_23@int@H_403_23@ i = mid + 1@H_403_23@; i <= right; ++ right_max)
            right_max @H_403_23@= sum;
    }
    @H_403_23@return@H_403_23@ left_max + right_max;
}@H_403_23@