函数merge_sort(1,n)的时间复杂度为

int divideConquer(int l,int r) {

if(l>r) return 0;

if(l==r) {

b[l]=c[l]=a[l];

return max(0,a[l]);

}

int mid=(l+r)/2;

int lans=divideConquer(l,mid);

int rans=divideConquer(mid+1,r);

int ret=max(lans,rans);

ret=max(ret,c[mid]+b[mid+1]);

int sum=0;

for(int i=l;i<=r;++i) {

sum+=a[i];

b[l]=max(b[l],sum);

}

sum=0;

for(int i=r;i>=l;--i) {

sum+=a[i];

c[r]=max(c[r],sum);

}

return ret;}