else {max2= A[high];max1=A[low];}
}
else
{
SecondElement(A[low..high],x1,x2);
if(x1<=A[n]) { max2=max1; max1=A[n];}
else if(x2>=A[n]) { max2=x2; max1=x1; }
else { max2=A[n]; max1=x1; }
}
}
该算法的时间复杂度满足如下递归方程：T(n)=T(n-1)+2；T(2)=1。解得T(n)=2n-3。
作业二
一、名词解释：
1.MST 性质：G=(V,E)是连通带权图，U 是V 的真子集。如果(u,v)∈E ，且u ∈U ，v ∈V-U ，且在所有这样的边中，(u,v)的权c[u][v]最小，那么一定存在G 的一棵最小生成树，它以(u,v)为其中一条边。这个性质称为MST 性质。
2.子问题的重叠性质：递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质。
二、简答题：
1.简述动态规划算法求解的基本要素。 动态规划算法求解的基本要素包括：
（1）最优子结构是问题能用动态规划算法求解的前提；
（2）动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问
题时，只是简单地用常数时间查看一下结果，即重叠子问题。
2.备忘录方法和动态规划算法相比有何异同？简述之。
备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。
备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。
3.贪心算法求解的问题主要具有哪些性质？简述之。
贪心算法求解的问题一般具有二个重要的性质：一是贪心选择性质，这是贪心算法可行的第一个基本要素；另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。
三、算法编写及算法应用分析题：
1.设计求解如下最大子段和问题的动态规划算法。只需给出其递推计算公式即可。
最大子段和问题：给定由n 个整数（可能为负整数）组成的序列a 1a 2 … an ，求该序列形如Σi ≤k ≤j ak 的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义，所求的最优值为max{0, max1≤i ≤j ≤n Σi ≤k ≤j ak }。
答：下面给出求解该问题的动态规划算法中的递推计算公式。
记 b (j )=max1≤i ≤j {Σi ≤k ≤j ak }，1≤j ≤n ，则所求最大子段和为max1≤j ≤nb (j )。而计算b [j ]的递推计算公式为：
b (0)=0 b (j )=max{b (j -1)+aj , aj }， 1≤j ≤n 。
该算法的时间复杂度为O(n )；空间复杂度为O(n )。
2.关于多段图问题。设G ＝(V ，E)是一个赋权有向图，其顶点集V 被划分成k>2个不相交的子集V i ：1i k ≤≤，其中，V 1和V k 分别只有一个顶点s （称为源）和一个顶点t （称为汇），图中所有的边（u,v ），i u V ∈，
1i v V +∈。求由s 到t 的最小成本路径。
（1）给出使用动态规划算法求解多段图问题的基本思想。 （2）使用上述方法求解如下多段图问题。
