动态规划(二)的.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * 设 F(i)表示以第i个数结尾的最大连续和 以第i个数结尾的最大连续和序列，可能存在两种选择： 情形一：只包含Ai 情形二：包含Ai和以Ai-1结尾的最大连续和序列 状态转移方程如下： F(i)=max{Ai , F(i-1)+Ai} 边界：F(1)=A1，Ans=max{F(i)|1=i=n} 该算法的时间复杂度为O(n) 分析 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 算法一——枚举 设 F(i)为以Ai结尾长度不超过M的最大子序和 对于每个F(i)，从1到m枚举k的值，完成Aj的累加和取最大值。 该算法的时间复杂度为O(n2) Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 简化方程 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 用一个二叉堆来维护S(i-k)，每次求F(i)之前的操作如下： 算法二——堆 求F(i-1)时，求min{S(i-m-1), ……,S(i-2)} 求F(i)时， 求min{S(i-m),……,S(i-1)} ☆在堆中删除元素S(i-m-1)，插入元素S(i-1).复杂度O(2log2n) ☆从堆中取出当前最小值.复杂度O(1) 所以计算的总复杂度为O(nlog2n) Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 队列优化 在算法二中，考虑用队列来维护决策值S(i-k)。每次只需要在队首删掉S(i-m-1)，在队尾添加S(i-1) 。但是取最小值操作还是需要O(n)时间复杂度的扫描。 考察在添加S(i-1)的时候，设现在队尾的元素是S(k)，由于ki-1，所以S(k)必然比S(i-1)先出队。若此时S(i-1)=S(k)，则S(k)这个决策永远不会在以后用到，可以将S(k)从队尾删除掉（此时队列的尾部形成了一个类似栈的结构） Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 队列优化 同理，若队列中两个元素S(i)和S(j)，若ij且S(i)=S(j)，则我们可以删掉S(i)（因为S(i)永远不会被用到）。此时的队列中的元素构成了一个单调递增的序列，即： S1S2S3……Sk Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 算法三 我们来整理在求F(i)的时候，用队列维护S(i-k)所需要的操作： ☆若当前队首元素S(x)，有xi-m，则S(x)出队；直到队首元素S(x)有x=i-m为止。 ☆若当前队尾元素S(k)=S(i-1)，则S(k)出队；直到S(k)S(i-1)为止。 ☆在队尾插入S(i-1) ☆取出队列中的最小值，即队首元素。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 算法三 由于对于求每个F(i)的时候，进队和出队的元素不止一个。 但是我们可以通过分摊分析得知，每一个元素S(i)只进队一次、出队一次，所以队列维护的时间复杂度是O(n)。而每次求F(i)的时候取最小值操作的复杂度是O(1)，所以这一步