算法分析习题参考标准答案五
————————————————————————————————作者：————————————————————————————————日期：
1．最大子段和问题：给定整数序列 n a a a ,,,21 ，求该序列形如 j
i
k k a 的子段和
的最大值：
j
i k k n j i a 1max ,0max
1) 已知一个简单算法如下：
int Maxsum(int n,int a,int& best i,int& bestj){ int sum = 0;
for (int i=1;i<=n;i++){ int suma = 0;
for (int j=i;j<=n;j++){ suma + = a[j]; if (suma > sum){ sum = suma; besti = i; bestj = j; } }
}
return sum;
}试分析该算法的时间复杂性。
2) 试用分治算法解最大子段和问题，并分析算法的时间复杂性。
3) 试说明最大子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。
（提示：令1()max
,1,2,,j
k
i j n
k i
b j a j n L ）
解：1）分析按照第一章，列出步数统计表，计算可得)(2
n O
2）分治算法：将所给的序列a[1:n]分为两段a [1:n/2]、a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有三种可能： ①a[1:n]的最大子段和与a[1:n/2]的最大子段和相同； ②a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同； ③a[1:n]的最大子段和为两部分的字段和组成，即
j n j
i
l n i j
a a a a a
122；
intMaxSubSum ( int *a, int left , int right){
int sum =0;
if( left==right)
sum = a[left] > 0? a[ left]:0 ;
else
{int center = ( left + right) /2;
int leftsum =MaxSubSum ( a, left , center) ;
int rightsum =MaxSubSum ( a, center +1, right) ;
int s_1 =0;
int left_sum =0;
for ( int i = center ; i >= left; i--){
left_sum + = a [ i ];
if( left_sum > s1)
s1 = left_sum;
}
int s2 =0;
int right_sum =0;
for ( int i = center +1; i <= right ; i++){
right_sum + = a[ i];
if( right_sum > s2)
s2 = right_sum;
}
sum = s1 + s2;
if ( sum < leftsum)
sum = leftsum;
if ( sum < rightsum)
sum = rightsum;
}
return sum;
}
int MaxSum2 (int n){
int a；
returnMaxSubSum ( a, 1, n) ;
} 该算法所需的计算时间T(n)满足典型的分治算法递归分式T(n)=2T(n/2)+O(n)，分治算法的时间复杂度为O(nlogn)
3）设}{max )(1 j i
k k j
i a j b ,则最大子段和为).(max max max max max 11111j b a a n
j j
i
k k j
i n j j i
k k n
j n i
},,,,max {)(11211j j j j j j j a a a a a a a a a j b
最大子段和实际就是)}(,),2(),1(max{n b b b .
要说明最大子段和具有最优子结构性质，只要找到其前后步骤的迭代关系即可。
}
,)1(max {},}{max max {},}{max {}{max )(1
1
11
11
1j j j j j i
k k j i j j i j j i k k j
i k k j i a a j b a a a a a a a j b
若0)1( j b , j a j b j b )1()(；
若0)1( j b ，j a j b )(。
因此，计算)(j b 的动态规划的公式为：.1},,)1(max {)(n j a a j b j b j j
intMaxSum (int* a ，int n ) {
int sum = 0, b = 0，j=0; for( int i=1;i<=n;i++) { if( b >0)
b = b + a [i];
else
b = a [i];
end{if} if( b > sum)
sum = b;
j=i ； end{if}
}
return sum; }
自行推导，答案：时间复杂度为O （n ）。
