本题考查的是分治法。
本题中将数组不断进行二分,这个过程的时间复杂度为O(log2n),划分后求解问题需要2个并列的for循环对划分后的数组进行求和比较,此时时间复杂度为O(n),划分和求和过程应该是嵌套的,所以时间复杂度综合为O(nlgn),本题应该选择A选项。
其算法过程可以设计如下:
int MaxSubSum(int *Array,int left ,int right){
int sum=0;
int i ;
if(left==right){/*分解到单个整数,不可继续分解*/
if(Array[left]>0)
sum=Array[left];
else
sum=0; //和小于等于0时,最大和记作0
}/*if*/
else{
/*从left和right的中间分解数组*/
int center=(left+right)/2; /*划分位置*/
int leftsum=MaxSubSum(Array,left,center);
int rightsum=MaxSubSum(Array,center+1,right);
/*计算包含center的最大值,判断是情形1(前半段)--Array[1...n]的最大子段和与Array[1...n/2]的最大子段和相同、情形2(后半段)--Array[1...n]的最大子段和与Array[n/2+1...n]的最大子段和、还是情形3(跨越中间元素)--Array[1...n]的最大子段和为Array[i...j]的最大子段和,且1≤i≤n/2,n/2+1≤j≤n。*/
int s1=0;
int lefts=0;
for(i=center;i>=left;i--){
lefts+=Array[i];
if(lefts<s1)
s1=lefts;
}/*for*/
int s2=0;
int rights=0;
for(i=center+1;i<=right;i++){
rights+=Array[i];
if(rights>s2)
s2=rights;
}/*for*/
sum=s1+s2;
/*情形1*/
if(sum<leftsum)
suml=leftsum;
/*情形2*/
if(sum<lrightsum)
suml=rightsum;
}/*else*/
return sum;
}