100/81．最大子段和问题：给定整数序列naaa,,,21，求该序列形如jikka的子段和的最大值：jikknjia1max,0max1)已知一个简单算法如下：intMaxsum(intn,inta,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++){intsuma=0;for(intj=i;j<=n;j++){suma+=a[j];if(suma>sum){sum=suma;besti=i;bestj=j;}}}returnsum;}试分析该算法的时间复杂性。2)试用分治算法解最大子段和问题，并分析算法的时间复杂性。3)试说明最大子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。（提示：令1()max,1,2,,jkijnkibjajn）解：1）分析按照第一章，列出步数统计表，计算可得)(2nO2）分治算法：将所给的序列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]的最大子段和为两部分的字段和组成，即jnjilnijaaaaa122；101/8intMaxSubSum(int*a,intleft,intright){intsum=0;if(left==right)sum=a[left]>0?a[left]:0;else{intcenter=(left+right)/2;intleftsum=MaxSubSum(a,left,center);intrightsum=MaxSubSum(a,center+1,right);ints_1=0;intleft_sum=0;for(inti=center;i>=left;i--){left_sum+=a[i];if(left_sum>s1)s1=left_sum;}ints2=0;intright_sum=0;for(inti=center+1;i<=right;i++){right_sum+=a[i];if(right_sum>s2)s2=right_sum;}sum=s1+s2;if(sum0)b=b+a[i];elseb=a[i];end{if}if(b>sum)sum=b;j=i；end{if}}returnsum;}自行推导，答案：时间复杂度为O（n）。103/82.动态规划算法的时间复杂度为O（n）（双机调度问题）用两台处理机A和B处理n个作业。设第i个作业交给机器A处理时所需要的时间是ia，若由机器B来处理，则所需要的时间是ib。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这n个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。以下面的例子说明你的算法：)4,3,11,4,8,3(),,,,,(),2,5,10,7,5,2(),,,,,(,6654321654321bbbbbbaaaaaan解：（思路一）删除（思路二）在完成前k个作业时，设机器A工作了x时间，则机器B最小的工作时间是x的一个函数。设F[k][x]表示完成前k个作业时，机器B最小的工作时间，则)}](1[,)](1[min{)]([kkaxkFbxkFxkF其中kbxkF)](1[对应第k个作业由机器B来处理（完成k-1个作业时机器A工作时间仍是x，则B在k-1阶段用时为)](1[xkF）；而)](1[kaxkF对应第k个作业由机器A处理（完成k-1个作业，机器A工作时间是x-a[k]，而B完成k阶段与完成k-1阶段用时相同为)](1[kaxkF）。则完成前k个作业所需的时间为)}]([,max{xkFx1）当处理第一个作业时，a[1]=2,b[1]=3;机器A所花费时间的所有可能值范围：0xa[0].x<0时，设F[0][x]=∞，则max(x,∞)=∞；0x<2时，F[1][x]=3，则Max(0,3)=3，x2时，F[1][x]=0，则Max(2,0)=2；2）处理第二个作业时：x的取值范围是：0<=x<=(a[0]+a[1])，当x<0时，记F[2][x]=∞；以此类推下去104/8（思路三）假定n个作业的集合为nSn,,2,1。设J为nS的子集，若安排J中的作业在机器A上处理，其余作业在机器B上处理，此时所用...
