求时间复杂度问题
int MaxSubSum(int *a,int left,int right)
{
int sum = 0;
if(left == right)
return sum = a[left-1] > 0 ?a[left-1] : 0;
int center = (left+right)/2;
int leftsum = MaxSubSum(a,left,center);
int rightsum = MaxSubSum(a,center+1,right);
int s1=0;
int lefts = 0;
for(int i=center; i>=left; i--)
{
lefts+=a[i-1];
if(lefts > s1)
s1 = lefts;
}
int s2 = 0;
int rights = 0;
for(int i=center+1; i<=right; i++)
{
rights+=a[i-1];
if(rights > s2)
s2 = rights;
}
sum = s1+s2;
if(sum < leftsum)
sum = leftsum;
if(sum < rightsum)
sum = rightsum;
return sum;
}
时间复杂度为O(nlogn),求时间复杂度详细计算过程，谢谢~~~
[解决办法]
主定理。T(n)=2T(n/2)+O(n) => T(n)=O(nlogn)
