计算机科学导论-计算思维程序实践 课件 L10 算法：程序与计算系统的灵魂

第10章算法：程序与计算系统之灵魂本章导图算法：程序与计算系统之灵魂本章学习什么--理解算法类问题求解框架算法：程序与计算系统之灵魂算法：程序与计算系统之灵魂一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择序列求和问题求解为例算法---计算机与软件的灵魂。最早的算法：公元前3世纪，欧几里得《几何原本》，求最大公约数的辗转相除法算法是一个有穷规则的集合，它用规则规定了解决某一特定类型问题的运算序列，或者规定了任务执行或问题求解的一系列步骤。如音乐乐谱、太极拳谱等都可看作广义的算法什么是算法？算法的概念与特征数字序列求和问题算法Input:n个具有先后次序的数字序列D={d1,d2,...,dn}；Output:序列D的n个数字之和；Step1.令一个变量sum的值为0，令一个变量i的值为1；Step2.将Di累加到sum，并将i增加1；Step3.若i小于等于n转到Step2；否则输出sum，算法结束。算法的概念与特征算法的5个基本特征有穷性：一个算法在执行有穷步规则之后必须结束。确定性：算法的每一个步骤必须要确切地定义，不得有歧义性。输入：算法有零个或多个的输入。输出：算法有一个或多个的输出/结果，即与输入有某个特定关系的量。能行性：算法中有待执行的运算和操作必须是相当基本的(可以由机器自动完成)，并能在有限时间内完成。算法：程序与计算系统之灵魂一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择序列求和问题求解为例单位执行时间：执行一次基本运算所需的平均时间，用来做基本单位时间复杂度:如果一个问题的规模是n，求解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数，则T(n)称为这一算法的“时间复杂度”。基本参数n——问题规模，表明输入数据的规模大小把复杂性或运行时间表达为n的函数。算法获得结果需要多长时间?时间复杂度算法的时间复杂度分析算法的时间复杂度时间复杂度描述算法随输入数据规模增长时，运算次数的增长趋势。算法的时间复杂度与计算机的性能无关时间复杂度是衡量算法本身求解问题效率的一种度量标准。时间复杂度描述算法随输入数据规模增长时，运算次数的增长趋势。此处是线性增长趋势。算法分析时间复杂度分析示例算法10.1数字序列求和问题Input:n个具有先后次序的数字序列D[1...n]；Output:序列D的n个数字之和；Step1.令一个变量sum的值为0，令一个变量i的值为1；Step2.将Di累加到sum，并将i增加1；Step3.若i小于等于n转到Step2；否则输出sum，算法结束。Step1：2条赋值语句；Step2：2条加法语句（重复n次）；Step3：执行1条判断语句（重复n次），算法结束前，执行1条输出语句T(n)=2+2n+n+1=3n+3“大O记法”：渐进时间复杂度

n越大，低阶项和系数的影响越小

去掉低阶项和系数，再用O进行标记

“O”表示量级(order)，允许使用“=”代替“≈”，如3n2+4n+1=Ο(n2)。O(f(n))算法的时间复杂度分析渐进时间复杂度与大O记法算法10.1数字序列求和问题Input:n个具有先后次序的数字序列D[1...n]；Output:序列D的n个数字之和；Step1.令一个变量sum的值为0，令一个变量i的值为1；Step2.将Di累加到sum，并将i增加1；Step3.若i小于等于n转到Step2；否则输出sum，算法结束。T(n)=3n+3

=

O(n)指数量级：O(bn),O(n!)多项式量级：O(1),O(logn),O(n),O(nlogn),O(nb)算法分析不同的时间复杂度量级以1百万个单位时间为1秒时间复杂度问题规模nn=10n=100n=1000O(1)常数0.001毫秒0.001毫秒0.001毫秒O(logn)对数0.003毫秒0.006毫秒0.0096毫秒O(n)线性0.01毫秒0.1毫秒1毫秒O(nlogn)线性对数0.03毫秒0.66毫秒9.97毫秒O(n2)平方0.1毫秒10毫秒1秒O(2n)指数1毫秒4*1016年3.4*10287年O(n!)阶乘3.6秒2.9*10144年1.3*102555年算法：程序与计算系统之灵魂一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择最大子序列和问题求解为例数学建模是用数学语言描述实际现象的过程，即建立数学模型的过程。数学模型是对实际问题的一种数学表述，是对部分现实世界为某种目的而进行的一个抽象与简化的数学结构。问题抽象与数学建模算法类问题求解的第一步就是数学建模【示例】攀岩问题：小明在训练攀岩，下图记录了每分钟上升或下降的高度，共14分钟的数据，定义“连续时间上升高度”为某个时间点t1到另一个时间点t2之间上升与下降的数据总和，例如第7~10分钟内的上升高度为7+7-5+7=16，要求找出最大的“连续时间上升高度”。这个问题怎么求解呢?攀岩问题：抽象成“最大子序列和问题”,序列：一组具有先后顺序的整数。最优化问题：在给定的约束条件下,求解最优的方案使得目标最大化或最小化的问题。这个问题是最优化问题。不同时间上升/下降高度--

整数序列连续时间上升高度--

子序列和问题抽象与数学建模将社会/自然问题转化为数学问题

【示例】最大子序列和问题：已知一个数字序列，在其中找到一个连续的子序列，使得该子序列之和是所有的子序列和中的最大值。问题抽象与数学建模

最大子序列和问题的数学模型数学模型的四个核心要素：输入输出约束目标通过自然数及其下标将不同的数据关联起来，是算法类问题抽象的重要方法。任何子序列可由di,di+1,...,dj表达，其中i和j分别为子序列的起点和终点。问题抽象与数学建模数学模型，可发现问题求解的基本思路

任何子序列之和可用“数字序列求和算法”求出。所有可能的i和j的组合（1≤i≤j≤n）穷举了所有可能的子序列。所有可能的子序列之和的最大值是问题的解。

穷举/遍历算法：程序与计算系统之灵魂一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择最大子序列和问题求解为例数据结构是数据的逻辑结构、存储结构及其操作的总称，它提供了问题求解/算法的数据操纵机制。(数据的)逻辑结构(数据的)存储结构操作反映逻辑语义关系为便于计算系统处理为什么需要数据结构算法的数据结构及其操作数据的逻辑结构描述数据之间的逻辑语意关系；数据的存储结构是在反映数据逻辑关系的原则下，便于计算系统处理的物理结构常见逻辑结构：线性表、树、图。数据的逻辑结构与存储结构算法的数据结构及其操作用线性表描述攀岩问题用树描述家族谱系用图描述校园地图线性表：n（n≥0）个具有相同特性的数据节点构成的有限序列

树：一种逻辑上表现为一颗倒挂的树的结构

图：一种由节点和连接节点的边构成的结构

线性表（LinearList）是一种由n（n≥0）个具有相同特性的数据节点构成的有限序列，可以记为a1,a2...an，除了首尾元素，线性表中的每个元素都有一个直接前驱和一个直接后继，第一个元素只有直接后继，最后一个元素只有直接前驱。数据结构的目的是为算法提供数据操纵机制，这种操纵机制由数据结构的操作接口提供，表现形式为一批定义良好的函数集，这些函数集合构成了数据结构可供外部使用的操作接口。线性表及其操作接口算法的数据结构及其操作IS-EMPTY(L)如果线性表L的长度为0，则返回1，否则返回0；LENGTH(L)获得线性表L中元素的个数；L[i]或GET(L,i)获取线性表L中的第i个元素（1≤i≤n）；PRIOR(L,i)获取线性表L第i个元素的前驱元素（2≤i≤n）；NEXT(L,i)获取线性表L第i个元素的后继元素（1≤i≤n-1）；L[i]←x或UPDATE(L,i,x)将线性表L的第i个元素改为x；INSERT(L,i,x)在线性表L的位置i处插入元素x，原位置i及其后面的的元素都向后移动一个位置；DELETE(L,i)从线性表L中删除位置i处的元素，原位置i+1及其后面的的元素都向前移动一个位置。线性表的操作接口用顺序表存储数据时，元素在内存中是连续的。顺序表的元素在逻辑上的排列顺序和物理上是一致的，若i<j，元素aj在逻辑上和物理上都在ai之后。线性表的存储结构之一：顺序表算法的数据结构及其操作

链表的每个元素除了存储数据，还有一个指针保存了下一个元素的地址（称为next指针）。元素在内存中的位置不是连续的，访问元素时，只能从第一个元素开始，沿着next指针依次访问下一个元素

。线性表的存储结构之二：链表算法的数据结构及其操作顺序表的元素存取效率很高，因为顺序表支持随机存取。

随机存取：通过元素的逻辑地址直接计算元素的物理地址以便进行存取。顺序表的存储操作所需时间与问题规模n无关。顺序表和链表在存取操作上的差异算法的数据结构及其操作顺序表中元素的物理地址计算公式：元素的物理地址=顺序表开始物理地址+(元素逻辑地址-1)*元素占用字节数访问顺序表元素的时间复杂度：O(1)

链表的元素存储效率较低，因为链表仅支持顺序存取。

顺序存取：给定逻辑地址i，只能先依次访问第1、2...i-1个元素，才能访问第i个元素。链表的存取操作所需时间与问题规模n相关，n越大，访问后面的元素所需时间越长。链表中的元素地址无法直接计算，只能顺着链表元素去访问访问链表元素的时间复杂度：O(n)顺序表要保持物理存储位置上的连续性。删除第i个元素后，必须将第i+1到第n个元素向前移动一个位置（通过内存拷贝操作），以填补因删除第i个元素而留下的空位。顺序表和链表在删除操作上的差异算法的数据结构及其操作删除顺序表元素的时间复杂度：O(n)

链表的元素在物理存储上不要求是连续的。链表删除第i个元素后，将第i-1个元素的next指针改为第i+1个元素的地址。删除链表元素的时间复杂度：O(1)问题的输入：n个具有先后次序的数字组成的序列D={d1,d2,...,dn}。线性表：由n（n≥0）个具有相同特性的数据节点构成的有限序列。为最大子序列和问题选择合适的数据结构算法的数据结构及其操作

线性表与问题的输入高度吻合用顺序表的效率更高（1）以数学模型为基础，确定数据的组织结构；（2）根据组织结构选择一种合适的逻辑结构；（3）确定需要对数据进行哪些操作；（4）根据这些操作从备选的存储结构中选择一种能高效支持这些操作的存储结构。

数据结构设计的方法。算法：程序与计算系统之灵魂一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择最大子序列和问题求解为例顺序结构：“执行A，然后执行B”，是按顺序执行一条条规则或语句的一种结构。分支结构：“如果Q成立，那么执行A，否则执行B”

，Q是某些逻辑条件，即按条件判断结果决定执行哪些规则或语句的一种结构。循环结构：控制规则或语句多次执行的一种结构---迭代(iteration)循环结构又分为有界循环结构和条件循环结构。有界循环：“重复N次执行A”，其中N是一个整数。条件循环：某些时候称为无界循环，“重复执行A直到条件Q成立”或“当Q成立时反复执行A”，其中Q是条件。算法与程序的基本控制结构算法的控制结构及其表达方法算法的控制结构描述了算法的操作步骤，控制结构的设计反映了算法的思想

流程图的基本表示符号

矩形框：表示一组顺序执行的规则或者程序语句。菱形框：表示条件判断，并根据判断结果执行不同的分支。圆形框：表示算法或程序的开始或结束。箭头线：表示算法或程序的走向。算法的程序流程图表达方法算法的控制结构及其表达方法描述算法的方法：自然语言描述法、流程图、伪代码三种控制结构的流程图表达开始第1条规则或语句第n条规则或语句结束顺序结构的流程图算法的程序流程图表达方法算法的控制结构及其表达方法开始条件成立否？是否条件成立时执行的规则或语句结束条件不成立时执行的规则或语句分支结构的流程图循环结构的流程图初始化部分开始循环控制条件成立？修改部分需循环执行的规则或语句。即：循环体结束是否循环结束可能解：解的取值空间中任何可能的一个值。可能解与解空间算法的控制结构及其表达方法最大子序列和问题的可能解：任意符合1≤i≤j≤n的i和j都形成一个可能解.例:D[2...6]、D[3...9]都是问题的可能解。解空间：由问题的所有可能解构成的集合。最大子序列和问题的解空间：所有可能的i和j的组合构成的子序列的集合。解空间大小:Cn2=n(n+1)/2问题求解的过程：在解空间中搜索符合问题约束以及优化目标的解。最基本的算法：遍历-计算-验证（穷举法）。【示例】最大子序列和问题的穷举法思想穷举法求最大子序列和问题的流程图算法的控制结构及其表达方法穷举法：对问题的解空间进行遍历，对遍历中的每个可能解进行逐一验证，若某个可能解符合问题的约束条件和优化目标，则为该问题的最终解。将任意可能解表达为D[i...j]，1≤i≤j≤n；将i设计为外层循环结构的循环变量，j为内层循环结构的循环变量；在内循环中，用算法10.1求子序列D[i...j]之和；时间复杂度：O(n3)。

将思想/策略转变为“步骤”不同数据结构设计给算法带来不同的性能；若使用链表存储序列D，算法时间复杂度将变为O(n4)。算法的伪代码表达方法算法的控制结构及其表达方法伪代码符号伪代码：一种介于计算机语言和自然语言之间的语言，主要目的是以精确、简洁、易于理解的方式描述算法。比自然语言描述法更为精确，比流程图更简洁，更容易用程序设计语言实现。穷举法求最大子序列和问题的伪代码算法的控制结构及其表达方法算法10.2最大子序列和问题的穷举算法1Input:大小为n的顺序表D[1...n]2Output:顺序表D的最大子序列和3functionFIND-MAX-SUBSEQ-2(D[1...n])4begin5

res←-∞;

//初值为负无穷大

6

fori←1tondo//i为子序列起点

7

forj←itondo//j为子序列终点

8

sum←0

9

fork←itojdo//子序列求和

10

sum←sum+D[k]

11

endfor

12

res←MAX(res,sum)//MAX返回较大值

13

endfor

14

endfor

15

输出res16endbegin计算学科的学生不仅能够设计算法，而且会描述和表达算法，更要能读懂算法。最外层循环：枚举子序列起点。中间的循环：枚举子序列终点。最内层循环：计算子序列之和。时间复杂度为：

T(n)=O(n3)

穷举法优点：思路简单易于实现，只要分析清楚如何遍历解空间，计算可能解，然后验证可能解，即可设计出相应的算法。穷举法优缺点及其一般步骤算法的控制结构及其表达方法穷举法缺点：因为需要遍历所有的可能解，若解空间很庞大，效率会很低

。（1）建立问题的数学模型，需要明确四要素：输入、输出、约束、优化目标；（2）以数学模型为基础，选择合适的数据结构，数据结构要便于控制结构的操作；（3）以数学模型为基础，分析问题的解空间形式；（4）设计控制结构对解空间进行遍历，对于每个可能解，使用数学模型中的约束和优化目标进行验证以便找到符合要求的解；设计穷举法的一般步骤算法：程序与计算系统之灵魂一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择

优化思想之一：“累加和”相减算法优化与策略选择算法优化的基本方法是消除无效计算消除无效计算的三种手段：消除不必要遍历：利用问题的约束条件来控制遍历的范围，停止对非必要部分的遍历。消除重复计算：在遍历解空间的过程中，检查不同可能解的验证是否存在重复的计算，如果存在，则暂存已验证可能解的结果，将之用于另一个可能解的验证；优化解空间搜索策略：不使用穷举法这种直接遍历解空间的控制结构，而是利用一些行之有效的算法策略，设计更高效的解空间搜索策略。学习算法的过程：学习如何在众多算法策略中选择适合特定问题求解的策略。

算法优化与策略选择穷举法中的无效计算以i为起点的子序列：D[i...i]、D[i..i+1]、...、D[i...n]，每次都从第一个元素开始进行累加，存在大量重复运算。4begin5

res←-∞;

//初值为负无穷大

6

fori←1tondo//i为子序列起点

7

forj←itondo//j为子序列终点

8

sum←0

9

fork←itojdo//子序列求和

10

sum←sum+D[k]

11

endfor

12

res←MAX(res,sum)13

endfor

14

endfor

15

输出res16endbegin示例：D[1...13]之和与D[1...14]之和的重复计算算法优化与策略选择优化思想之一：“累加和”相减累加和序列S[0...n]：元素S[i]为序列D[1...n]中前i个元素之和。子序列D[i...j]之和=S[j]-S[i-1],1≤i≤j≤n。为什么可以提高效率：一次循环O(n)时间完成序列S的构造，一次减法O(1)时间计算任意子序列之和

利用“累加和”的优化算法算法优化与策略选择算法10.3最大子序列和问题的优化算法一1Input:大小为n的顺序表D[1...n]2Output:顺序表D的最大子序列和3functionFIND-MAX-SUBSEQ-3(D[1...n])

4begin5

初始化大小为n+1的序列S[0...n]6

S[0]←07

fori←1tondo//i为子序列起点8

S[i]←S[i-1]+D[i]//构造序列S的第i个元素9

endfor

10

res←-∞

//初值为负无穷大

11

fori←1tondo//i为子序列起点12

forj←itondo//以i为起点的第2到最后一个子序列的循环

13

sum←S[j]-S[i-1]//利用序列S计算子序列D[i...j]之和

14

res←MAX(res,sum)//确保res为最大值

15

endfor

16

endfor

17

输出res

18endbegin构造“累加和”序列S“累加和”一次构造，多次使用时间复杂度为：

T(n)=O(n2)

算法优化与策略选择算法10.3中的无效计算依然是对解空间中所有可能解进行遍历的算法10

res←-∞

//初值为负无穷大

11

fori←1tondo//i为子序列起点12

forj←itondo//以i为起点的第2到最后一个子序列的循环

13

sum←S[j]-S[i-1]//利用序列S计算子序列D[i...j]之和

14

res←MAX(res,sum)//确保res为最大值

15

endfor

16

endfor遍历解空间是最基本的问题求解方法。有很多巧妙的算法策略，可以更高效地在解空间中搜索问题的解，不需要遍历整个解空间。还有更好的办法吗算法：程序与计算系统之灵魂一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择

优化思想之二：问题分解算法优化与策略选择优化思想之二：问题分解问题分解是一种将大的问题分解为若干个更小的子问题的方法，如果子问题的形式与原问题相同，可用递归方法完成子问题的求解。子问题规模必须要小于原问题如果子问题的形式与原问题相同，可以利用递归求解子问题要建立原问题与子问题之间的联系要分析清楚什么是可以直接求解的最小子问题算法优化与策略选择最大值子序列和问题的分解原问题的解只可能是下面的三种情况之一：“解”完全在左半部分即D[1...7]中，因此结果等于f(1,7);“解”完全在右半部分即D[8...14]中，因此结果等于f(8,14);“解”跨越了中线，一部分在左半部分，另一部分在右半部分，记为g(1,7,14)。f(1,7)、f(8,14)与f(1,14)属于同类问题；g(1,7,14)属于新问题求出3个子问题的解，其中的最大值就是原问题的解算法优化与策略选择跨越中线子问题g(1,7,14)的求解方法以中线位置为起点向左进行累加，在累加过程中筛选左半部分的最大值lsum；以中线位置为起点向右进行累加，在累加过程中筛选右半部分的最大值rsum;g(1,7,14)的最终结果为lsum+rsum=25。上述两个累加操作的时间复杂度为O(n)。

跨越中线子问题的伪代码算法优化与策略选择算法10.4最大子序列和问题的优化算法二1Input:子序列的起点i、终点j、中间位置k2Output:跨越中线的最大的子序列和3functiong(i,k,j)//跨越中线的子问题4begin5lsum←-∞

//中线到左边的最大子序列6sum←07fort←kdowntoido8sum←sum+D[t]9lsum←MAX(lsum,sum)10endfor11rsum←-∞

//中线到右边的最大子序列12sum←013fort←k+1tojdo14sum←sum+D[t]15rsum←MAX(rsum,sum)16endfor17returnlsum+rsum18endbegin求左半部分最大值求右半部分最大值时间复杂度为：

T(n)=O(n)

算法优化与策略选择自顶向下分解形成分解树f类问题一直分解下去，形成最小子问题，最小子问题只有一个元素，元素的值就是解。g类问题每层都有，实际累加计算都发生在g类问题中。算法优化与策略选择子问题的解自底向上合并形成更大子问题的解最底层的f类问题、以及所有的g类问题都可直接求解，求最大值后可依次合并出上一层的解；一直进行下去，合并出原问题（最顶层）的解。基于“问题分解”的优化算法算法优化与策略选择算法10.4最大子序列和问题的优化算法二19Input:子序列的起点i、终点j20Output:子序列D[i...j]的最大的子序列和21functionf(D[1...n],i,j)//形式相同的子问题

22begin23ifi=jthen//最小子问题24returnD[i]25endif26k←⌊(i+j)/2⌋//计算中线位置27returnMAX(f(i,k),f(k+1,j),g(i,k,j))//从中线分解问题28endbegin29Input:大小为n的顺序表D[1...n]30Output:顺序表D的最大子序列和31functionFIND-MAX-SUBSEQ-4(D[1...n])32begin33res←f(1,n)//原问题34输出res35endbegin

最小子问题/递归函数出口调用递归函数求解问题问题分解与合并/递归调用时间复杂度是多少？算法优化与策略选择算法10.4的时间复杂度分析算法的分解树共有logn层每一层g函数处理的序列合并起来就是原序列，相当于对原序列进行了一次累加，是O(n)的操作。总的时间复杂度是O(nlogn)算法优化与策略选择算法10.4是分治策略分治策略是一种利用问题分解求解问题的策略，其核心思想是分而治之，求解问题时采用分、治、合三个步骤：分：将复杂问题分解为与原问题形式相同的、规模更小的独立子问题，子问题可以一直分解下去；治：直接求解最小子问题；合：将已经求解的子问题的解进行逐层合并，最后得到原问题的解。算法10.4的“分”：将问题分解为2个形式相同的子问题和1个形式不同的子问题；算法10.4的“治”：求解最小的f类子问题，以及g类子问题的解；算法10.4的“合”：合并f类问题和g类问题的解，得到上一层子问题的解。算法优化与策略选择算法10.4中的无效计算分解树共有logn层共对原序列进行了logn次重复的累加还有更好的办法吗算法：程序与计算系统之灵魂一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择

优化思想之三：解空间划分算法优化与策略选择优化思想之三：解空间划分将序列D[1...n]的所有子序列根据末尾元素的不同分为n个子集。例如，以D[3]结尾的子集为{D[3...3],D[2...3],D[1...3]}；分别对每个子集进行遍历并求出最大子序列和，记为T[1]、T[2]、...、T[n]，例如T[3]是子集{D[3...3],D[2...3],D[1...3]}的最大子序列和，结果为max(-20,-12,1)=1。序列T[1...n]中的最大值就是问题的解，T[10]为25，是序列T的最大值，因此是问题的解。如何提高效率：如果生成序列T的效率高，算法的效率就很高算法优化与策略选择求序列T的方案一：穷举法一个T[i]的计算方法：遍历所有“以第i个元素结尾的子序列”（起点为k=1，2，...i），分别计算其元素之和，然后取最大值为结果：T[i]=max(S[i]-S[k-1]),k=1,2,...i，S[0...n]为“累加和”序列。所有T[i]的计算方法：i从1循环到n，依次计算T[i]。求一个T[i]需要进行i次减法运算，时间复杂度为O(n)求所有T[i]的时间复杂度为O(n2)，比算法10.4更差算法优化与策略选择求序列T的方案二：优化方案T[i]=max(S[i]-S[k-1]),k=1,2,...i(k是子序列起点，i是终点)若能找到所有S[k-1]中的最小值，即可得到S[i]-S[k-1]的最大值，即：T[i]=S[i]-min(S[k-1]),k=1,2,...i

构造最小累加和序列M，令M[i]为序列S[0...i]的最小值，则M[i-1]为序列S[0...i-1]的最小值，即min(S[k-1])，则：

T[i]=S[i]-M[i-1]序列M的生成方式：M[i]=min(M[i-1],S[i])M序列的生成可在O(n)时间内完成求一个T[i]需要进行1次减法运算，时间复杂度为：O(1)求所有T[i]的时间复杂度为O(n)，比算法10.4更优基于“解空间划分”的优化算法算法优化与策略选择构造“累加和”序列S构造序列T时间复杂度为：

T(n)=

O(n)

构造序列M序列T的最大值为问题的解算法10.5最大子序列和问题的优化算法三1Input:大小为n的顺序表D[1...n]2Output:顺序表D的最大子序列和3functionFIND-MAX-SUBSEQ-5(D[1...n])

4begin5初始化大小为n+1的序列S[0...n]和M[0...n]6初始化大小为n的序列T[1...n]7S[0]←08

fori←1tondo9S[i]←S[i-1]+D[i]//构造序列S的第i个元素10endfor

11M[0]←012

fori←1tondo13M[i]←MIN(M[i-1],S[i])//构造序列M的第i个元素14endfor

15

fori←1tondo16

T[i]←S[i]-M[i-1]//利用序列S和序列M计算T[i]

17

endfor

18

res←-∞

//最终结果，初值为负无穷大

19

fori←1tondo20

res←MAX(res,T[i])

21

endfor

22

输出res

23endbegin算法优化与策略选择算法10.5的空间优化：省略序列T最终目的是找出所有T[i]中的最大值；每次完成S[i]-M[i-1]计算时，不保存到T[i]

，直接与res竞争；去掉构造序列T的循环，并省略序列T1

res←-∞

2

fori←1tondo3

res←MAX(res,S[i]-M[i-1])

4

endfor计算结果不保存到T[i]，直接与res竞争18

res←-∞

19

fori←1tondo20

res←MAX(res,T[i])

21

endfor算法优化与策略选择算法