问答题
设有n个不全为负的整型元素存储在一维数组A[n]中，它包含很多连续的子数组，例如数组A={1，-2，3，10，-4，7，2，-5}，请设计一个时间上尽可能高效的算法，求出数组A的子数组之和的最大值(例如数组A的最大的子数组为{3，10，-4，7，2}，因此输出为该子数组的和18)。要求：
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
【正确答案】
【答案解析】[另解1] (1)算法的基本思想：
采用分治法。数组(A[0]，A[1]，…，A[n-1])分为长度相等的两段数组(A[0]，…，A[n/2])以及(A[n/2+1]，…，A[n-1])，分别求出这两段数组各自的最大子段和，则原数组(A[0]，A[1]，…，A[n-1])的最大子段和分为以下3种情况：
1)(A[0]，A[1]，…，A[n-1])的最大子段与(A[0]，…，A[n/2])的最大子段相同。
2)(A[0]，A[1]，…，A[n-1])的最大子段与(A[n/2+1]，…，A[n-1])的最大子段相同。
3)(A[0]，A[1]，…，A[n-1))的最大子段跨过(A[0]，…，A[n/2])与(A[n/2+1]，…，A[n-1])。
如果数组元素全部为负，结果返回0。
①设置left，right。初始化为原数组的开始和结束位置。设置mid=(left+right)/2，指向数组的中间位置。
②如果left=right，返回元素值和0的较大者。
③计算A[left...mid]中包含A[mid]的最大连续数组及其值Lmax。计算A[mid+1...right]中包含A[mid+1]的最大连续数组及其值Rmax。求出跨过中间元素时的最大子段及其最大值Lmax+Rmax。递归求出A[left...mid]中的最大连续子数组及其最大值，与A[mid+1...right]的最大连续子数组及其最大值。返回三者之中的最大值。
(2)算法的实现如下：
int MaxSum(int *A, int left, int right){
if(left==right){ //递归退出条件，只有一个元素
return msx(A[left], 0); //返回元素值与0较大者。
int mid=(left+right)/2; //mid是数组的中间位置，分治开始
int Lmax=0; //求(A[left]，...，A[mid])中包含A[mid]子数组的最大值
int Lsum=0; //Lmax是左边最大和，Lsum是累加和
for(int i=mid; i＞=left; i--){
Lsum+=A[i]; //从A[mid]往左累加
if(Lsum＞Lmax) //比较
Lmax=Lsum;
}
int Rmax=0; //求(A[mid+1]，...，A[right])中包含A[mid+1]子数组的最大值
int Rsum=0; //Rmax是右边最大和，Rsum是累加和
for(int i=mid+1; i＜=right; i++){
Rsum+=A[i]; //从A[mid+1]往右累加
if(Rsim＞Rmax) //比较
Rmax=Rsum;
}
//递归求1)2)情况下的连续子数组最大和。并返回1)2)3)种情况下的最大值。
//Lmax+Rmax为第三种情况下连续子数组最大和。
//MaxSum(A. left, mid)递归求A[left...mid]的连续予数组最大和。
//Maxsum(A, mid+1, right)递归求A[mid+1, right]连续子数组最大和。
return max(Lmax+Rmax, max(MaxSum(A, left, mid), MaxSum(A, mid+1, right)));
}
(3)时间复杂度的计算公式为T(n)=2*T(n/2)+n，因此时间复杂度为O(n*log 2 n)。递归树的高度为log 2 n，每层空间辅助变量为常数，因此空间复杂度为O(log 2 n)。
[另解2] 使用暴力破解。假设最大的一段数组为A[i]，…，A[j]，则对i=0～n-1 j=i～n-1，遍历一遍，求出最大的Sum(i，j)即可。长度为n的数组有O(n 2 )个子数组，求一个长n的数组和的时间复杂度为O(n)，因此时间复杂度为O(n 3 )，因此性能较差，空间复杂度为O(1)。 [解析] 采用动态规划法。若记
，1≤i≤j≤n，则所求最大子段和为：
采用分治法。数组(A[0]，A[1]，…，A[n-1])分为长度相等的两段数组(A[0]，…，A[n/2])以及(A[n/2+1]，…，A[n-1])，分别求出这两段数组各自的最大子段和，则原数组(A[0]，A[1]，…，A[n-1])的最大子段和分为以下3种情况：
1)(A[0]，A[1]，…，A[n-1])的最大子段与(A[0]，…，A[n/2])的最大子段相同。
2)(A[0]，A[1]，…，A[n-1])的最大子段与(A[n/2+1]，…，A[n-1])的最大子段相同。
3)(A[0]，A[1]，…，A[n-1))的最大子段跨过(A[0]，…，A[n/2])与(A[n/2+1]，…，A[n-1])。
如果数组元素全部为负，结果返回0。
①设置left，right。初始化为原数组的开始和结束位置。设置mid=(left+right)/2，指向数组的中间位置。
②如果left=right，返回元素值和0的较大者。
③计算A[left...mid]中包含A[mid]的最大连续数组及其值Lmax。计算A[mid+1...right]中包含A[mid+1]的最大连续数组及其值Rmax。求出跨过中间元素时的最大子段及其最大值Lmax+Rmax。递归求出A[left...mid]中的最大连续子数组及其最大值，与A[mid+1...right]的最大连续子数组及其最大值。返回三者之中的最大值。
(2)算法的实现如下：
int MaxSum(int *A, int left, int right){
if(left==right){ //递归退出条件，只有一个元素
return msx(A[left], 0); //返回元素值与0较大者。
int mid=(left+right)/2; //mid是数组的中间位置，分治开始
int Lmax=0; //求(A[left]，...，A[mid])中包含A[mid]子数组的最大值
int Lsum=0; //Lmax是左边最大和，Lsum是累加和
for(int i=mid; i＞=left; i--){
Lsum+=A[i]; //从A[mid]往左累加
if(Lsum＞Lmax) //比较
Lmax=Lsum;
}
int Rmax=0; //求(A[mid+1]，...，A[right])中包含A[mid+1]子数组的最大值
int Rsum=0; //Rmax是右边最大和，Rsum是累加和
for(int i=mid+1; i＜=right; i++){
Rsum+=A[i]; //从A[mid+1]往右累加
if(Rsim＞Rmax) //比较
Rmax=Rsum;
}
//递归求1)2)情况下的连续子数组最大和。并返回1)2)3)种情况下的最大值。
//Lmax+Rmax为第三种情况下连续子数组最大和。
//MaxSum(A. left, mid)递归求A[left...mid]的连续予数组最大和。
//Maxsum(A, mid+1, right)递归求A[mid+1, right]连续子数组最大和。
return max(Lmax+Rmax, max(MaxSum(A, left, mid), MaxSum(A, mid+1, right)));
}
(3)时间复杂度的计算公式为T(n)=2*T(n/2)+n，因此时间复杂度为O(n*log 2 n)。递归树的高度为log 2 n，每层空间辅助变量为常数，因此空间复杂度为O(log 2 n)。
[另解2] 使用暴力破解。假设最大的一段数组为A[i]，…，A[j]，则对i=0～n-1 j=i～n-1，遍历一遍，求出最大的Sum(i，j)即可。长度为n的数组有O(n 2 )个子数组，求一个长n的数组和的时间复杂度为O(n)，因此时间复杂度为O(n 3 )，因此性能较差，空间复杂度为O(1)。 [解析] 采用动态规划法。若记
，1≤i≤j≤n，则所求最大子段和为：